> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/design/1032.-stream-of-characters.md).

# 1032. Stream of Characters

Implement the `StreamChecker` class as follows:

* `StreamChecker(words)`: Constructor, init the data structure with the given words.
* `query(letter)`: returns true if and only if for some `k >= 1`, the last `k` characters queried (in order from oldest to newest, including this letter just queried) spell one of the words in the given list.

**Example:**

```
StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // init the dictionary.
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
```

**Note:**

* `1 <= words.length <= 2000`
* `1 <= words[i].length <= 2000`
* Words will only consist of lowercase English letters.
* Queries will only consist of lowercase English letters.
* The number of queries is at most 40000.

```cpp
class StreamChecker {
public:
    class TrieNode {
    public:
        TrieNode() : next(26, nullptr), isWord(false) {}
        ~TrieNode() {
            for (auto& p : next) {
                if (p) delete p;
            }
        }
        void buildTrie(const vector<string>& words, int& max_len) {
            for (const string& w : words) {
                int len = w.length();
                max_len = max(max_len, len);
                TrieNode* cur = this;
                for (int i = len - 1; i >= 0; --i) {
                    char c = w[i];
                    if (!cur->next[c - 'a']) cur->next[c - 'a'] = new TrieNode();
                    cur = cur->next[c - 'a'];
                }
                cur->isWord = true;
            }
        }
        vector<TrieNode*> next;
        bool isWord;
    };
    StreamChecker(vector<string>& words) : max_len(0), root(new TrieNode() ) {
        root->buildTrie(words, max_len);
    }
    ~StreamChecker() {
        delete root;
    }
    bool query(char letter) {
        str += letter;
        if (str.length() > max_len) str.erase(str.begin());
        TrieNode* cur = root;
        for (int i = str.length() - 1; i >= 0 && cur; --i) {
            char c = str[i];
            cur = cur->next[c - 'a'];
            if (cur && cur->isWord) return true;
        }
        return false;
    }
private:
    int max_len;
    TrieNode* root;
    string str;
};
```