Stream of Characters — Reverse Suffix Trie

Problem

Design a system where query(letter) returns true if any word from the list ends at the current stream position.

Approach — Reverse Trie + Deque of Active Nodes

Insert all words reversed into trie. Maintain list of active trie nodes. For each new letter, advance all active nodes; add root as new candidate.

Time: O(Q * total words) worst | Space: O(total word chars)

Solutions

Python

class StreamChecker:
    def __init__(self, words: list[str]):
        self.root={}
        for w in words:
            node=self.root
            for c in reversed(w):
                if c not in node: node[c]={}
                node=node[c]
            node['#']=True
        self.stream=[]
    def query(self, letter: str) -> bool:
        self.stream.append(letter)
        node=self.root
        for c in reversed(self.stream):
            if c not in node: return False
            node=node[c]
            if '#' in node: return True
        return False

Complexity

Time: O(max_word_len) per query (stream bounded by max word len)
Space: O(total word chars)