Coding Interview PatternsStream of Characters
HardTrie
Stream of Characters
Explanation & Solution
Description
Design a StreamChecker class that initializes with a list of words and provides a query method.
For each call to query(letter), the method should return true if any suffix of the characters queried so far (including the current character) matches any word in the given list.
Implement the class using a trie built from the reversed words, so that each query checks suffixes efficiently.
Input:operations = ["StreamChecker","query","query","query","query","query","query","query","query","query","query","query","query"], operands = [[["cd","f","kl"]],["a"],["b"],["c"],["d"],["e"],["f"],["g"],["h"],["i"],["j"],["k"],["l"]]
0
StreamChecker
1
query
2
query
3
query
4
query
5
query
6
query
7
query
8
query
9
query
10
query
11
query
12
query
Output:[null,false,false,false,true,false,true,false,false,false,false,false,true]
0
null
1
false
2
false
3
false
4
true
5
false
6
true
7
false
8
false
9
false
10
false
11
false
12
true
Explanation: After querying "c" then "d", the suffix "cd" matches. After querying "f", the suffix "f" matches. After querying "k" then "l", the suffix "kl" matches.
Constraints
1 <= words.length <= 20001 <= words[i].length <= 200words[i]consists of lowercase English lettersletteris a lowercase English letter- At most
4 * 10⁴calls will be made toquery
Approach
Trie pattern
1. Build a Reverse Trie
- For each word in the dictionary, insert its reversed version into a trie
- This allows us to match suffixes of the stream by traversing the trie from the most recent character backward
- Track the maximum word length to limit how far back we search
2. Maintain a Stream Buffer
- Keep an array
streamthat stores every character queried so far - Each call to
query(letter)appends the letter to this buffer
3. Check Suffixes on Each Query
- Starting from the latest character in the stream, traverse backward through the buffer
- At each step, follow the corresponding child in the reverse trie
- If we reach a node marked as
_end, a word matches the current suffix — returntrue - If no child exists for the current character, return
false - Only check up to
maxLencharacters back for efficiency
4. Process All Operations
- Parse the operations array:
"StreamChecker"creates the instance,"query"calls the query method - Collect results in an array and return them
Key Insight
- By building a trie from reversed words, each query becomes a backward traversal from the end of the stream. This elegantly converts a suffix-matching problem into a prefix-matching problem on the reversed trie.
Time
O(M) per query where M is the max word lengthSpace
O(T + Q) where T is total characters in all words and Q is total queries