问题
给定一个字符串列表,从列表中找出出现在给定文本中的字符串。
示例
list = ['red', 'hello', 'how are you', 'hey', 'deployed']
text = 'hello, This is shared right? how are you doing tonight'
result = ['red', 'how are you', 'hello']
'red'是因为它包含'shared'且'shared'是'red'的子字符串。
- 这非常类似于这个问题,只是我们需要查找的单词也可以是子字符串。
- 该列表相当大,并随着用户数量的增加而增加,与文本长度基本相同。
- 我考虑采用一种解决方案,其中时间复杂度取决于文本的长度而不是单词列表,以便在添加大量用户时可扩展。
解决方案
- 从给定的单词列表构建一个trie树
- 在文本上运行dfs,检查当前单词是否与trie树匹配
伪代码
def FindWord (trie, text, word_so_far, index):
index > len(text)
return
//Check if the word_so_far is a prefix of a key; if not return
if trie.has_subtrie(word) == false:
return
//Check if the word_so_far is a key; if ye add to result and look further
if trie.has_key(word) == false:
// Add to result and continue
//extend the current word we are searching
FindWord (trie, text, word_so_far + text[index], index + 1)
//start new from the next index
FindWord (trie, text, "", index + 1)
这种方法的问题在于,虽然运行时间现在取决于len(text)
,但是在构建Trie后,它的时间复杂度为O(2^n)
,这是一次性的多个文本也可以,所以没问题。
我也没有看到任何重叠的子问题可以进行记忆化并提高运行时间。
你能否建议一种方式,可以实现根据给定文本而不是单词列表进行运行时,并且可以对其进行预处理和缓存,比这个还要更快。