Stream of Characters

hard trie reversed trie suffix matching

Problem

Design an algorithm that accepts a stream of characters and checks, after each new character, whether some suffix of the characters received so far spells a word from a given dictionary. Implement query(letter) which returns true if the letters seen so far end with any dictionary word.

Inputwords = ["cd", "f", "kl"], queries = "abcd"

Output[false, false, false, true]

After 'd' the stream ends with "cd", a dictionary word, so the fourth query returns true.

words (comma-separated)

query stream (letters)

class StreamChecker:
    def __init__(self, words):
        self.trie = {}
        self.stream = []
        for w in words:
            node = self.trie
            for c in reversed(w):
                node = node.setdefault(c, {})
            node["$"] = True

    def query(self, letter):
        self.stream.append(letter)
        node = self.trie
        for c in reversed(self.stream):
            if c not in node:
                return False
            node = node[c]
            if "$" in node:
                return True
        return False

class StreamChecker {
  constructor(words) {
    this.trie = {};
    this.stream = [];
    for (const w of words) {
      let node = this.trie;
      for (let i = w.length - 1; i >= 0; i--) {
        const c = w[i];
        node = node[c] || (node[c] = {});
      }
      node["$"] = true;
    }
  }

  query(letter) {
    this.stream.push(letter);
    let node = this.trie;
    for (let i = this.stream.length - 1; i >= 0; i--) {
      const c = this.stream[i];
      if (!(c in node)) return false;
      node = node[c];
      if (node["$"]) return true;
    }
    return false;
  }
}

class StreamChecker {
    private Map<Character, Object> trie = new HashMap<>();
    private StringBuilder stream = new StringBuilder();

    public StreamChecker(String[] words) {
        for (String w : words) {
            Map<Character, Object> node = trie;
            for (int i = w.length() - 1; i >= 0; i--) {
                char c = w.charAt(i);
                node = (Map<Character, Object>) node.computeIfAbsent(c, k -> new HashMap<>());
            }
            node.put('$', Boolean.TRUE);
        }
    }

    public boolean query(char letter) {
        stream.append(letter);
        Map<Character, Object> node = trie;
        for (int i = stream.length() - 1; i >= 0; i--) {
            char c = stream.charAt(i);
            if (!node.containsKey(c)) return false;
            node = (Map<Character, Object>) node.get(c);
            if (node.containsKey('$')) return true;
        }
        return false;
    }
}

struct Node { unordered_map<char, Node*> next; bool end = false; };

class StreamChecker {
    Node* trie = new Node();
    string stream;
public:
    StreamChecker(vector<string>& words) {
        for (auto& w : words) {
            Node* node = trie;
            for (int i = (int)w.size() - 1; i >= 0; i--) {
                char c = w[i];
                if (!node->next.count(c)) node->next[c] = new Node();
                node = node->next[c];
            }
            node->end = true;
        }
    }

    bool query(char letter) {
        stream.push_back(letter);
        Node* node = trie;
        for (int i = (int)stream.size() - 1; i >= 0; i--) {
            char c = stream[i];
            if (!node->next.count(c)) return false;
            node = node->next[c];
            if (node->end) return true;
        }
        return false;
    }
};

Explanation

After every new letter, we must check whether the stream ends with some dictionary word. The clever idea is to store the words in a reversed trie — each word inserted back to front — so that matching a suffix becomes matching a prefix.

When building, we walk each word from its last letter to its first with reversed(w), creating trie nodes, and mark the end with node["$"] = True.

On query(letter), we add the letter to the stream, then walk the trie starting from the newest letter and going backwards. If a letter is missing from the current node, no dictionary word ends here, so we stop. If we ever step onto a node carrying "$", some word matched and we return True.

Example: words ["cd", "f", "kl"], stream a, b, c, d. After d, we walk back d → c in the reversed trie (because cd was stored as d→c) and hit the end marker, so the answer is true.

Walking backwards only as far as the longest word makes each query fast, and reversing the trie is what turns "ends with" into a simple downward walk.

Time: O(L) per query Space: O(Σ|word|)