class StreamChecker:
def __init__(self, words: List[str]):
# time O(NM) N numer of words, M max length of word space O(NM) worst
# step1: initialize trie and stream {}
# step2: for each word in words: reversely add to trie
self.trie = {}
self.stream = collections.deque([])
for word in words: # set(words) if there are duplicates
cur = self.trie
for ch in word[::-1]:
if ch not in cur:
cur[ch] = {}
cur = cur[ch]
cur['$'] = word
def query(self, letter: str) -> bool:
# time O(M) max length word in words space O(M)
# step1: appendleft to stream
self.stream.appendleft(letter)
# step2: get node from trie; iterate ch from stream ; (1) check if node['$'] exist; if yes return True. (2) check if ch in the node , if no, return False. (3) go deeper down trie
node = self.trie
for ch in self.stream:
if '$' in node:
return True
if ch not in node:
return False
node = node[ch]
return '$' in node
# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)