Stream Of Characters - Leetcode Solution

The Stream of Characters problem on LeetCode is:

You are given a 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) spell one of the words in the given list.

In other words, you need to implement a class that takes in a list of words and can check if the last k characters queried spell out one of the words in the list, where k is any positive integer.

Solution:

The first thing to notice is that we can't simply check if the last k characters queried match one of the words. For example, if we have the words ["ab", "bc", "cd"] and the stream "abcd", we can't simply check the last 2 characters "cd" as they belong to multiple words.

Therefore, we need to check every prefix of the queried characters to see if it matches any of the words in the list. We can use a trie data structure to store the words in a way that allows for efficient prefix matching.

We can initialize the trie with the words in the constructor of the StreamChecker class. We also need a variable to store the characters that have been queried so far.

When we call the query(letter) function, we append the new letter to the queried characters. We then traverse the trie starting from the root and following the path that corresponds to the queried characters in reverse order. If we reach a node in the trie that corresponds to the end of a word, we know that the queried characters spell out that word.

To make this process more efficient, we can store the children of each node in the trie as a dictionary. This allows us to quickly find the next node to traverse based on the current character.

Here's the Python code for the StreamChecker class:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class StreamChecker:
    def __init__(self, words: List[str]):
        self.root = TrieNode()
        self.query_chars = []
        for word in words:
            curr = self.root
            for c in reversed(word):
                if c not in curr.children:
                    curr.children[c] = TrieNode()
                
                curr = curr.children[c]
            
            curr.is_end_of_word = True
    
    def query(self, letter: str) -> bool:
        self.query_chars.append(letter)
        curr = self.root
        for c in reversed(self.query_chars):
            if c not in curr.children:
                return False
            curr = curr.children[c]
            if curr.is_end_of_word:
                return True
        
        return False

The time complexity of this solution is O(nm^2) where n is the number of words and m is the maximum length of a word. This is because we need to insert each word into the trie, which takes O(m^2) time in the worst case (if all words have the same prefix), and we need to traverse the trie for each query, which takes O(m) time in the worst case. The space complexity is O(nm) as we need to store each word in the trie.

1