#1032 Stream of Characters - Solution

Problem Statement

Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words.

For example, if words = ["abc", "xyz"] and the stream added the four characters (one by one) 'a', 'x', 'y', and 'z', your algorithm should detect that the suffix "xyz" of the characters "axyz" matches "xyz" from words.

Implement the StreamChecker class:

StreamChecker(String[] words) Initializes the object with the strings array words.
boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.

Example 1:

Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]

Explanation
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // return False
streamChecker.query("b"); // return False
streamChecker.query("c"); // return False
streamChecker.query("d"); // return True, because 'cd' is in the wordlist
streamChecker.query("e"); // return False
streamChecker.query("f"); // return True, because 'f' is in the wordlist
streamChecker.query("g"); // return False
streamChecker.query("h"); // return False
streamChecker.query("i"); // return False
streamChecker.query("j"); // return False
streamChecker.query("k"); // return False
streamChecker.query("l"); // return True, because 'kl' is in the wordlist

Constraints:

1 <= words.length <= 2000
1 <= words[i].length <= 200
words[i] consists of lowercase English letters.
letter is a lowercase English letter.
At most 4 * 10⁴ calls will be made to query.

The key challenge in #1032 Stream of Characters is efficiently checking whether the current stream of queried characters forms a suffix that matches any word from a given dictionary. Since queries arrive one character at a time, repeatedly scanning all words would be too slow.

A common strategy is to use a Trie (prefix tree), but with a twist: store each word in reversed order. As characters arrive from the stream, maintain a running buffer of recent characters and traverse the Trie from the newest character backward. This effectively converts the suffix-matching problem into a prefix search inside the Trie.

If during traversal you reach a node marked as the end of a word, a match exists. This approach significantly reduces repeated comparisons and allows quick incremental checks for each query.

With a well-structured Trie and bounded stream length, each query can be processed efficiently while keeping memory usage manageable.

Approach	Time Complexity	Space Complexity
Reversed Trie with Stream Buffer	O(L) per query, where L is the maximum word length	O(N * L) for storing words in the Trie

Solutions (4)

Approach 1: Trie with Reverse Words

This approach utilizes a reversed Trie (prefix tree) to efficiently manage and query suffixes of input characters. By storing the reversed words in a Trie, we can match suffixes of the input stream by querying from the current character backwards. For each character queried, we move through the Trie from those characters up to a certain limit (or until no further match) to see if any of the suffixes match one of the stored words.

Time Complexity for insertion: O(N*L), where N is the number of words and L is the maximum length of a word.
Time Complexity for queries: O(Q*L) where Q is the number of queries and L is the maximum length of a word.
Space Complexity: O(N*L) for storing the words in the Trie.

Python Java

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_end_of_word = False
5
6class StreamChecker:
7    def __init__(self, words):
8        self.root = TrieNode()
9        self.stream = []
10        for word in words:
11            node = self.root
12            for char in reversed(word):
13                if char not in node.children:
14                    node.children[char] = TrieNode()
15                node = node.children[char]
16            node.is_end_of_word = True
17
18    def query(self, letter):
19        self.stream.append(letter)
20        node = self.root
21        for char in reversed(self.stream):
22            if node.is_end_of_word:
23                return True
24            if char not in node.children:
25                return False
26            node = node.children[char]
27        return node.is_end_of_word

Explanation

The implementation involves creating a Trie that stores each word in reverse. When a query is made, characters are added to a list representing the current stream. We then check from the current end of the stream backwards through the Trie to determine if any suffix matches a word.

Approach 2: Aho-Corasick Automaton

The Aho-Corasick algorithm is useful for searching multiple 'dictionary' words within a text. We build an automaton with all words and query the stream letters. This data structure enables matching of all dictionary words in parallel through a finite state machine that jumps quickly between states even upon mismatches.

Time Complexity for building: O(N*L), because we insert and construct failure links.
Time Complexity for queries: O(Q*L) leveraging finite state machine transitions.
Space Complexity: O(N*L) due to the state-space storage representing words.

C++JavaScript

1#include <vector>
2#include <queue>
3#include <unordered_map>
4using namespace std;
5
class AhoCorasick {
public:
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        TrieNode* fail = nullptr;
        bool is_end = false;
    };

    TrieNode *root = new TrieNode();

    void insert(const string &word) {
        TrieNode *node = root;
        for(char c : word) {
            if(!node->children.count(c)) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->is_end = true;
    }

    void build() {
        queue<TrieNode*> q;
        root->fail = root;
        for(auto &p : root->children) {
            p.second->fail = root;
            q.push(p.second);
        }
        while(!q.empty()) {
            TrieNode *curr = q.front(); q.pop();
            for(auto &p : curr->children) {
                char c = p.first;
                TrieNode *child = p.second;
                TrieNode *fail = curr->fail;
                while(fail != root && !fail->children.count(c)) {
                    fail = fail->fail;
                }
                if(fail->children.count(c)) {
                    child->fail = fail->children[c];
                } else {
                    child->fail = root;
                }
                child->is_end |= child->fail->is_end;
                q.push(child);
            }
        }
    }
};

class StreamChecker {
    AhoCorasick ac;
    AhoCorasick::TrieNode* node;
    public:
    StreamChecker(vector<string>& words) {
        for(const string &word : words) {
            ac.insert(word);
        }
        ac.build();
        node = ac.root;
    }

    bool query(char letter) {
        while(node != ac.root && !node->children.count(letter)) {
            node = node->fail;
        }
        if(node->children.count(letter)) {
            node = node->children[letter];
        }
        return node->is_end;
    }
};