题目描述

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.

题意：按下述要求实现 StreamChecker 类：

StreamChecker(words)：构造函数，用给定的字词初始化数据结构。
query(letter)：如果存在某些 k >= 1，可以用查询的最后 k个字符（按从旧到新顺序，包括刚刚查询的字母）拼写出给定字词表中的某一字词时，返回 true。否则，返回 false。

算法1

(Trie树)

题解：这道题是需要让我们判断最近的k个字符是不是在字典中，其实我们可以首先把所有的单词逆序插入Trie树，然后我们将每次添加的字符组成的字符串逆序在Trie树中查找，如果某条路径上的点是单词节点，我们就返回True。

如样例：我们先将["dc","f","lk"]插入Trie树，然后依次在Trie树依次查找["a","ba","cba","dcba","edcba",..."lkjihgfedcba"]，只要当前路径上有一个单词节点就直接返回true，如果某一步找不到就返回false。

但是这题最坑的地方在于，由于查询次数很多，最后字符串很大，如果我们全部保存的话会报MLE，所以我们必须只保留部分字符，假设字典中最长的单词长度为n，那么我们只需要保存最新的n的字符。

C++ 代码

class StreamChecker {
public:
    int son[100000][26] = {},cnt[100000] = {},idx = 0,len = 0;
    string cur = "";
    void insert(string &s)
    {
        int n = s.length(),p = 0;
        len = max(len,n);
        for(int i = n - 1; i >= 0 ; i --)
        {
            int u = s[i] - 'a';
            if(!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p] ++;
    }
    StreamChecker(vector<string>& words) {
        for(auto word:words) insert(word);
    }

    bool query(char letter) {
        cur = letter + cur;
        int p = 0,n = cur.size();
        if(n > len){n --;cur.erase(cur.end() - 1);};
        for(int i = 0 ; i < n ; i ++)
        {
            int u = cur[i] - 'a';
            if(son[p][u]) p = son[p][u];
            else return false;
            if(cnt[p] > 0) return true;
        }
        return false;
    }
};