Stream of Characters

Design StreamChecker: given a list of words, query(c) returns true if any suffix of characters queried so far is in the word list.

Example 1

StreamChecker(["cd","f","kl"]), query(a)→false, query(c)→false, query(d)→true

Solution Approach

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.

Java

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)