1032. Stream of Characters

https://leetcode.com/problems/stream-of-characters/description/

给一个由字符组成stream, 问每次steam遇到的新字符和前面流过的字符组成的词是否出现在了给定的字典里。查字典用Trie。把所有出现过的字符记录下来存成一个字符串s，要求的是s末尾字符能否和前面组成词，正着给s断词非常麻烦。倒着来生成Trie和查询即可。

/*
 * @lc app=leetcode id=1032 lang=cpp
 *
 * [1032] Stream of Characters
 *
 * https://leetcode.com/problems/stream-of-characters/description/
 *
 * algorithms
 * Hard (42.81%)
 * Likes:    130
 * Dislikes: 32
 * Total Accepted:    7.3K
 * Total Submissions: 16.9K
 * Testcase Example:  '["StreamChecker","query","query","query","query","query","query","query","query","query","query","query","query"]\n[[["cd","f","kl"]],["a"],["b"],["c"],["d"],["e"],["f"],["g"],["h"],["i"],["j"],["k"],["l"]]'
 *
 * 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:
        vector<TrieNode*> children;
        bool word;
        TrieNode(): children(26), word(false) {}
    };
    TrieNode *root;
    string s;
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        TrieNode *node;
        for (const auto &w : words) {
            node = root; 
            for (int i = w.size() - 1; i >= 0; --i) {
                const int idx = w[i] - 'a';
                if (node->children[idx] == nullptr) node->children[idx] = new TrieNode();
                node = node->children[idx];
            }
            node->word = true;
        }
    }
    
    bool query(char letter) {
        s.push_back(letter);
        auto node = root;
        for (int i = s.size() - 1; i >= 0 && node != nullptr; --i) {
            node = node->children[s[i] - 'a'];
            if (node != nullptr && node->word) return true;
        }
        return false;
    }
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */