streamChecker.query("a"); // stream： a
streamChecker.query("b"); // stream：ab
streamChecker.query("c"); // stream：abc
之后我们用拼接的单词在 words 中查询即可， 最简单的方式当然是每次 query 都去扫描一次，这种方式时间复杂度为 $O(m n q)$，其中 m 和 n 分别为 words 的长度和， words[i] 的平均长度，m 和 n 最大为 2000，q 是待查项，最大为 40000， 毫无疑问会超时。
我们可以采用构建 Trie 的形式，即以空间环时间， 其代码和常规的 Trie 类似，只需要将 search(word) 函数做一个简单修改即可，我们不需要检查整个 word 是否存在， 而已 word 的前缀存在即可。
提示：可以通过对 words 去重，来用空间换区时间。
具体算法：
init 中 构建 Trie 和 双端队列 stream
query 时，往 stream 的左边 append 即可。
调用 Trie 的 search（和常规的 search 稍有不同， 我上面已经讲了）
以上面的例子为例：
streamChecker.query("a"); // stream： a
streamChecker.query("b"); // stream：ab
streamChecker.query("c"); // stream：abc
当 query("c") 的时候，我们需要查 abc，bc， c 三个是否有一个在 words 中。由于我们知道待查项的尾字符（在这个例子中尾字符是 c），因此从尾字符开始在前缀树中搜索，看是否能够搜索到 word 即可。这提示我们前缀树倒序插入或者 stream 倒序插入。
class StreamChecker:
def __init__(self, words: List[str]):
self.trie = Trie()
self.stream = deque([])
for word in set(words):
self.trie.insert(word[::-1])
def query(self, letter: str) -> bool:
self.stream.appendleft(letter)
return self.trie.search(self.stream)
关键点解析
前缀树模板
倒序插入
代码
语言支持: Python
Python Code:
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.Trie = {}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
curr = self.Trie
for w in word:
if w not in curr:
curr[w] = {}
curr = curr[w]
curr['#'] = 1
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
curr = self.Trie
for w in word:
if w not in curr:
return False
if "#" in curr[w]:
return True
curr = curr[w]
return False
class StreamChecker:
def __init__(self, words: List[str]):
self.trie = Trie()
self.stream = deque([])
for word in set(words):
self.trie.insert(word[::-1])
def query(self, letter: str) -> bool:
self.stream.appendleft(letter)
return self.trie.search(self.stream)
