[LeetCode] 1032. Stream of Characters

[grandyang]

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.

这道题让实现一个流检查器的类，给了一个单词数组当作构造器的参数，然后还要实现一个 query 的功能，每次提供一个新的字符，问当前的字符流中的某个前缀子串是是否是给定的某个单词。说实话这道题的描述比较难理解，博主研究了好久才总算搞明白。由于给定的单词可能有很多，每当加入一个新的字符，都去遍历所有的单词肯定是不尊重 OJ 的解法，会超时。所以只能寻求更加高效的解法，仔细研究题目的要求，���以发现一旦加入了新的字符，query 函数能返回 true 的情况一定是当前字符串的某个前缀正好是某个单词了，这种玩字符串前缀的题目不难让人联想到前缀树 Trie，又叫字典树，之前就一道专门关于 Trie 的题目 Implement Trie (Prefix Tree)，这里用完全相同的思路。首先就是定义这个 Trie 结点，定义成结构体或者类都可以，这里博主就直接定义为结构体了，里面有两个变量，一个是布尔型 isWord，标记前缀是否是一个完整单词，另一个是 next 数组，里面有 26 个 Trie 结点，指向下一个字符。声明前缀树的根结点 root，定义字符串 queryStr。在构建函数中，其实就是构建这个前缀树，遍历每个单词，从最后的字符开始处理，若当前结点的 next 数组中对应位置不包含该字符，则新建出 Trie 结点，然后当前结点移到新建的结点继续循环，完成之后标记 isWord 为 true。实现 query 函数时进行类似的操作，先把字符加入 queryStr，然后从其末尾往前遍历，取出 next 数组中对应位置的结点，若存在且 isWord 为 true，则说明找到了某个单词，直接返回 true，否则继续遍历。最终没找到的话返回 false 即可，参见代码如下：

class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        for (string word : words) {
            TrieNode *node = root;
            for (int i = (int)word.size() - 1; i >= 0; --i) {
                if (!node->next[word[i] - 'a']) {
                    node->next[word[i] - 'a'] = new TrieNode();
                }
                node = node->next[word[i] - 'a'];
            }
            node->isWord = true;
        }
    }
    
    bool query(char letter) {
        queryStr.push_back(letter);
        TrieNode *node = root;
        for (int i = (int)queryStr.size() - 1; i >= 0 && node; --i) {
            node = node->next[queryStr[i] - 'a'];
            if (node && node->isWord) return true;
        }
        return false;
    }
    
private:
    struct TrieNode {
        bool isWord;
        TrieNode *next[26];
    };
    
    TrieNode *root = new TrieNode();
    string queryStr;
};

Github 同步地址:

#1032

类似题目：

Implement Trie (Prefix Tree)

参考资料：

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

https://leetcode.com/problems/stream-of-characters/discuss/278769/Java-Trie-Solution

https://leetcode.com/problems/stream-of-characters/discuss/278250/Python-Trie-Solution-with-Explanation

LeetCode All in One 题目讲解���总(持续更新中...)