Design StreamChecker: given a list of words, query(c) returns true if any suffix of characters queried so far is in the word list.
StreamChecker(["cd","f","kl"]), query(a)→false, query(c)→false, query(d)→true
Build reversed Trie from all words. Maintain a queue of active Trie nodes. On each query, advance nodes and add new start nodes.
- Insert all words reversed into Trie.
- Maintain a list of active Trie search positions.
- On query(c): add root to candidates list; advance each candidate node by character c.
- If any candidate reaches a word end, return true.
import java.util.*;
class StreamChecker {
TrieNode root = new TrieNode();
Deque<TrieNode> active = new ArrayDeque<>();
public StreamChecker(String[] words) {
for (String w : words) {
TrieNode node = root;
for (int i = w.length()-1; i >= 0; i--) {
char c = w.charAt(i);
if (node.ch[c-'a']==null) node.ch[c-'a'] = new TrieNode();
node = node.ch[c-'a'];
}
node.isEnd = true;
}
}
public boolean query(char letter) {
Deque<TrieNode> next = new ArrayDeque<>();
next.offer(root);
for (TrieNode node : active) {
if (node.ch[letter-'a'] != null) next.offer(node.ch[letter-'a']);
}
active = next;
for (TrieNode n : active) if (n.isEnd) return true;
return false;
}
static class TrieNode { TrieNode[] ch=new TrieNode[26]; boolean isEnd; }
}
- Time Complexity: query: O(N) per query (N=words built), build: O(sum of word lengths)
- Space Complexity: O(W*L)