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.

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;
};