Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words. For example, if words = [“abc”, “xyz”] and the stream added the four characters (one by one) ‘a’, ‘x’, ‘y’, and ‘z’, your algorithm should detect that the suffix “xyz” of the characters “axyz” matches “xyz” from words. Implement the StreamChecker class:
StreamChecker(String[] words) Initializes the object with the strings array words.
boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.
Example 1: Input [“StreamChecker”, “query”, “query”, “query”, “query”, “query”, “query”, “query”, “query”, “query”, “query”, “query”, “query”] [[[“cd”, “f”, “kl”]], [“a”], [“b”], [“c”], [“d”], [“e”], [“f”], [“g”], [“h”], [“i”], [“j”], [“k”], [“l”]] Output [null, false, false, false, true, false, true, false, false, false, false, false, true] Explanation StreamChecker streamChecker = new StreamChecker([“cd”, “f”, “kl”]); streamChecker.query(“a”); // return False streamChecker.query(“b”); // return False streamChecker.query(“c”); // return False streamChecker.query(“d”); // return True, because ‘cd’ is in the wordlist streamChecker.query(“e”); // return False streamChecker.query(“f”); // return True, because ‘f’ is in the wordlist streamChecker.query(“g”); // return False streamChecker.query(“h”); // return False streamChecker.query(“i”); // return False streamChecker.query(“j”); // return False streamChecker.query(“k”); // return False streamChecker.query(“l”); // return True, because ‘kl’ is in the wordlist
- code
class StreamChecker:
def __init__(self, words: List[str]):
self.trie = {}
self.stream = deque()
for word in set(words):
node = self.trie
for ch in word[::-1]:
if ch not in node:
node[ch] = {}
node = node[ch]
node['$'] = ''
def query(self, letter: str) -> bool:
self.stream.appendleft(letter)
node = self.trie
for ch in self.stream:
if '$' in node:
return True
if not ch in node:
return False
node = node[ch] # ch in node, cur char is in the leaf, go back
return '$' in node
- code TLE
class StreamChecker:
def __init__(self, words: List[str]):
self.stack = []
self.words = words
self.init_word_stack(words)
def query(self, letter: str) -> bool:
flag = False
middle_stack = []
for word_stack in self.stack:
if letter == word_stack[-1]:
word_stack.pop()
if not word_stack:
flag = True
else:
middle_stack.append(word_stack)
self.init_word_stack(self.words)
if middle_stack:
self.stack.extend(middle_stack)
return flag
def init_word_stack(self, words):
self.stack = []
for word in words:
word_stack = [] # abc => c,b,a
for char in reversed(word):
word_stack.append(char)
self.stack.append(word_stack)