1032. 字符流-526互联

方法：字典树

解题思路

理解题意：每一次查询是对从最开始到当前的字符组成的字符串\(str\)查询\(words\)数组中是否有字符串是\(str\)的后缀；
对于字符串的查找使用字典树，每次查询的时间复杂度为\(O(L)，L = max{word.length()}\)，大大降低查找字符串的时间消耗；
字典树详解。

注意：由于题目中的\(word\)都是小写字母，可以和\(0-25\)数字对应，就可以直接用数组存储当前节点的\(children\)，若使用\(map\)存储较数组访问会慢的多。但有些题目不满足本题的条件，就只能选择\(map\)存储，比如：1233. 删除子文件夹—题解。

代码

class Trie {
private:
    vector<Trie*> children;
    int fid = -1; // fid != -1时，表示此节点为某字符串的终点，存储当前word在words中的idx

public:
    Trie () {
        children.resize(26);
    }

    void insert(int fid, string &word) {
        Trie* node = this; // 方便后续节点插入操作
        reverse(word.begin(), word.end());
        for (auto &c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) { // 该子节点未被加入到trie中
                node->children[idx] = new Trie();
            }
            node = node->children[idx]; // 变更父节点，从而插入下一个节点
        }
        node->fid = fid; // 到达该字符串终点，设置fid
    }

    bool search(string &str) {
        Trie* node = this;
        for (int i = str.size() - 1; i >= 0; i --) {
            int idx = str[i] - 'a';
            if (!node->children[idx]) return false; // 当前后缀匹配过程中不存在字符str[i]
            node = node->children[idx];
            if (node->fid != -1) return true;
        }
        return false;
    }
};

class StreamChecker {
private:
    Trie* trie = new Trie();
    string str;
public:
    StreamChecker(vector<string>& words) {
        for (int i = 0; i < words.size(); i ++ ) {
            trie->insert(i, words[i]);
        }
    }
    
    bool query(char letter) {
        str += letter;
        return trie->search(str);
    }
};

复杂度分析

StreamChecker()
时间复杂度：\(O(nL)，n = words.size()，L = max{word.length()}\)；
空间复杂度：\(O(1)\)。
query()
时间复杂度：\(O(L)\)；
空间复杂度：\(O(1)\)。

characters leetcode stream 1032