LeetCode Solutions Blog

Stream of Characters

Number: 1097

Difficulty: Hard

Paid? No

Problem Description

Design an algorithm to process a stream of characters so that upon each new character you can determine whether any suffix of the stream matches one of the words in a given list. Each query returns true if any non-empty suffix of the current stream forms one of the words.

Key Insights

Instead of checking all possible suffixes against every word, we store words in a Trie data structure.
Since we are matching suffixes, it is efficient to insert the words in reversed order. This way, when a new character is queried, we traverse the stream backward and the Trie forward.
Limit the size of the stored stream to the length of the longest word.
The worst-case query cost is proportional to the maximum length of words.

Space and Time Complexity

Time Complexity: O(M) per query, where M is the maximum length of the words. Space Complexity: O(Total characters in all words) for the Trie plus O(M) for the stream buffer.

Solution

We construct a reverse Trie where each word from the list is stored in reverse order. With every query, append the new character to a stream buffer and traverse this list backwards while matching against the Trie. If at any point you hit a Trie node marked as the end of a word, return true. The stream buffer length is capped at the length of the longest word to ensure efficient memory usage. This method drastically reduces unnecessary comparisons and quickly identifies valid suffixes.

Code Solutions

# Python implementation of StreamChecker
class StreamChecker:
    def __init__(self, words: list[str]):
        # Build a reverse Trie, where each node is a dictionary
        self.trie = {}
        self.max_length = 0  # maximum length of a word in words
        for word in words:
            self.max_length = max(self.max_length, len(word))
            node = self.trie
            # Insert word in reverse order
            for char in reversed(word):
                if char not in node:
                    node[char] = {}
                node = node[char]
            # Mark the end of a word
            node['#'] = True
        self.stream = []  # buffer to store characters from query

    def query(self, letter: str) -> bool:
        # Append the new letter to our stream buffer
        self.stream.append(letter)
        # Keep the stream buffer size within the maximum word length
        if len(self.stream) > self.max_length:
            self.stream.pop(0)

        node = self.trie
        # Traverse the stream backwards (i.e., the most recent characters)
        for ch in reversed(self.stream):
            if ch not in node:
                return False  # no further matching path in Trie
            node = node[ch]
            # Check if we have reached the end of a word
            if '#' in node:
                return True
        return False

# Example usage:
# streamChecker = StreamChecker(["cd", "f", "kl"])
# print(streamChecker.query("a"))
# print(streamChecker.query("b"))
# print(streamChecker.query("c"))
# print(streamChecker.query("d"))