DSA problem
Stream of Characters
Design an algorithm that accepts a stream of characters and checks if a suffix of the string seen so far is a string from a given list of words. Implement the StreamChecker class:
StreamChecker(String[] words) initializes the data structure with the given list of dictionary words. boolean query(char letter) accepts a new character from the stream and returns true if any non-empty suffix of the characters queried so far spells one of the dictionary words.
The challenge is that the natural way to test "is any word a suffix of the current stream?" — comparing every word against the tail of the stream on each query — is far too slow when both the dictionary and the stream are large. We need a structure that answers each query in time proportional to the longest word, not to the total number of words.
The optimal trick is to insert the dictionary words into a Trie in REVERSED order. Then we maintain a rolling buffer of the last few stream characters and, on every query, walk the Trie backwards through the buffer. At each step we ask the Trie "is there a (reversed) word ending here?" — if yes, return true; if there is no child for the next character, stop. Since each word in the Trie is at most L characters long, every query costs O(L) regardless of stream length or dictionary size.
Examples
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]][null, false, false, false, true, false, true, false, false, false, false, false, true]["StreamChecker", "query", "query", "query"]
[[["ab"]], ["a"], ["b"], ["c"]][null, false, true, false]["StreamChecker", "query", "query"]
[[["hello"]], ["h"], ["i"]][null, false, false]Constraints
- 1 <= words.length <= 2000
- 1 <= words[i].length <= 200
- words[i] consists of lowercase English letters.
- letter is a lowercase English letter.
- At most 4 * 10^4 calls will be made to query.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.