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: