Solution: Stream of Characters

Explore how to implement a StreamChecker class that determines if any suffix of an incoming stream matches words from a list by using a reversed Trie structure. Learn to insert reversed words into a Trie, manage a character stream with a deque, and efficiently query suffix matches through Trie traversal. This lesson helps you understand the design of custom data structures for dynamic suffix detection, balancing time and space complexity in streaming scenarios.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

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 = ["cat"] 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 ...