# 1032. Stream of Characters
Implement the StreamChecker class as follows:
StreamChecker(words): Constructor, init the data structure with the given words.
query(letter): returns true if and only if for some k >= 1, the last k characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.
Example:
StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary.
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
# Solution
Approach 1: use a trie to keep all the words. At query time, keep a list of current possible trie nodes to search down.
Approach 2: construct an index of words by its last charater. At query time, check the suffix of the queried sequence.
# Code (Python)
Approach 1:
class TrieNode:
def __init__(self):
self.is_word = False
self.children = {} # can also use an array of 26 chars
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: 'str') -> 'None':
cur = self.root
for char in word:
if char not in cur.children:
cur.children[char] = TrieNode()
cur = cur.children[char]
cur.is_word = True
class StreamChecker:
def __init__(self, words: List[str]):
# time: O(num_words * avg_word_length)
self.trie = Trie()
for word in words:
self.trie.insert(word)
self.currents = []
def query(self, letter: str) -> bool:
# time for each query: O(len_query)
result = False
self.currents.append(self.trie.root)
new_currents = []
for current_node in self.currents:
if not current_node.children:
continue
if letter in current_node.children:
new_currents.append(current_node.children[letter])
if new_currents[-1].is_word:
result = True
self.currents = new_currents
return result
Approach 2:
import collections
class StreamChecker:
def __init__(self, words: List[str]):
# idea: check query suffixes
self.all_queries = ''
self.index = collections.defaultdict(set)
for word in words:
# index words by its last letter (or last 2 letters, 3 letters...)
self.index[word[-1]].add(word)
def query(self, letter: str) -> bool:
# time: O(avg_length)
self.all_queries = self.all_queries + letter
for word in self.index[letter]:
if self.all_queries.endswith(word):
return True
return False
# Code (C++)
Approach 1:
Approach 2: