[LeetCode] 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.

这道题让实现一个流检查器的类,给了一个单词数组当作构造器的参数,然后还要实现一个 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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中...)

上一篇:实战:一文带你解决Mysql主从复制日常错误


下一篇:PAT 乙级 1032 挖掘机技术哪家强 (20分)