Course4all
Join us on telegram
Home/dsa/Trie/Stream of Characters

Stream of Characters

Master this topic with zero to advance depth.

Stream of Characters

Design a data structure that accepts a stream of characters and checks if any suffix of the characters queried so far is in a given list of words.

Hard

Examples

Input: words = ["cd","f","kl"], streamQueries = ["a", "b", "c", "d", "e", "f"]
Output: [false, false, false, true, false, true]
Approach 1

Level I: Brute Force Suffix Comparison

Intuition

Store all arrived characters in a list. For every query, iterate through all words in the dictionary and check if any word matches the current suffix of the character stream. O(N * L) per query.

⏱ O(N * L) per query.💾 O(Total Chars)
java
class StreamChecker {
    List<String> words; StringBuilder sb = new StringBuilder();
    public StreamChecker(String[] words) { this.words = Arrays.asList(words); }
    public boolean query(char letter) {
        sb.append(letter); String s = sb.toString();
        for (String w : words) if (s.endsWith(w)) return true;
        return false;
    }
}
Approach 2

Level III: Reverse Trie

Intuition

Since we need to match a suffix of the stream, it's efficient to store the dictionary words in a Trie in reversed order. As new characters arrive in the stream, we store them in a buffer (or current path). To check if any suffix matches, we traverse the reversed Trie starting from the last character received.

⏱ O(L) per query (L is max word length).💾 O(N * L).
java
class StreamChecker {
    class Node { Node[] children = new Node[26]; boolean isEnd = false; }
    Node root = new Node();
    StringBuilder sb = new StringBuilder();
    public StreamChecker(String[] words) {
        for (String w : words) {
            Node curr = root;
            for (int i = w.length() - 1; i >= 0; i--) {
                int c = w.charAt(i) - 'a';
                if (curr.children[c] == null) curr.children[c] = new Node();
                curr = curr.children[c];
            }
            curr.isEnd = true;
        }
    }
    public boolean query(char letter) {
        sb.append(letter);
        Node curr = root;
        for (int i = sb.length() - 1; i >= 0 && i >= sb.length() - 2000; i--) {
            int c = sb.charAt(i) - 'a';
            if (curr.children[c] == null) return false;
            curr = curr.children[c];
            if (curr.isEnd) return true;
        }
        return false;
    }
}
← Previous QuestionBoggle Game
Next Question →Longest Word in Dictionary through Deleting