Solution: Stream of Characters

Statement

Design a data structure that processes a stream of characters and, after each character is received, determines if a suffix of these characters is a string in a given array of strings words.

For example, if words = ["dog"] and the stream adds the characters $\text{`d', `c', `a'}$, and $\text{`t'}$ in sequence, the algorithm should detect that the suffix "cat" of the stream "dcat" matches the word "cat" from the list.

So, for words, the goal is to detect if any of these words appear as a suffix of the stream built so far. To accomplish this, implement a class StreamChecker:

• Constructor: Initializes the object with the list of target words.

• boolean query(char letter): Appends a character to the stream and returns TRUE if any suffix of the stream matches a word in the list words.

Constraints:

• $1\leq$ words.length $\leq 1000$

• $1 \leq$ words[i].length $\leq 200$

• words[i] consists of lowercase English letters.

• letter is a lowercase English letter.

• At most $4 * 10^2$ calls will be made to query.

Solution

This problem requires checking whether any suffix of a growing stream of characters matches any string from words. The core challenge lies in the uncertainty of how many characters from the end of the stream should be compared—should it be the last one, two, or ten? A naive approach would try all possibilities, which is computationally expensive. The elegant and optimized solution lies in constructing a custom data structure that combines a Trie (prefix tree), which is ideal for dynamic string matching, with a dynamic stream buffer.

However, while Tries are naturally suited for prefix matching, this problem requires suffix matching. To overcome this mismatch, we reverse all words before inserting them into the Trie. This transformation allows us to treat suffixes of the input stream as prefixes when read in reverse, converting the problem into a standard Trie traversal.

While inserting each reversed word into the Trie, we store a special terminal marker '$' at the end of the path representing the full word. This sentinel value indicates that a valid word ends at that node. During queries, if we reach a node that contains '$', we immediately know that the characters traversed from the stream form a string from the words.

To manage the stream in reverse order, so that the most recent character is always checked first, we use a deque (double-ended queue). This allows constant-time insertion at the front as new characters arrive. Each time a new character is queried, we walk through the Trie using characters from the stream. If we encounter a '$' marker during traversal, we return TRUE to indicate a successful match. If a character is not found in the current Trie path, we return FALSE, as no word can match the current suffix.

Now, let’s look at the solution steps below:

1. Constructor:

   1. We initialize a trie to store the reversed words and use a deque named stream to track the queried characters in reverse order.

   2. For each unique word in the words list:

      1. We reverse the word to align it with the direction of suffix matching.

      2. We insert the reversed characters one by one into the Trie.

      3. At the end of each word’s path in the Trie, we mark it with a sentinel key '$', indicating a complete word.

2. boolean query(char letter):

   1. We append the incoming character, letter, to the front of the stream, keeping the most recent character at the beginning.

   2. Next, we begin traversing the trie from the root, using characters from the stream:

      1. If we encounter the sentinel '$', we return TRUE immediately, as a valid word from words has been matched.

      2. If a character is not found in the current trie node, we return FALSE, since no further match is possible.

      3. Otherwise, we continue matching character by character through the Trie.

Let’s look at the following illustration to get a better understanding of the solution: