XTAO's Tech Blog
0%

[Leetcode]1032. Stream of Characters (C++)

发表于 更新于 分类于 评论数：
3.9k 4 分钟

题目描述

题目链接：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.

例子

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.

解题思路

这道题可以考虑成一道查找单词的题，一般查找单词的题可以考虑用字典树（前缀树）来实现。包括以下两种思路。

方法一

首先我想到的是正向的字典树，即每个单词从头到尾插入树中。查找的时候维护一个候选单词队列，候选队列中永远包含树的头。查找时对每一个候选节点进行查找下一个字母所在位置，如果可以进行到下一层则放入新的候选队列中，另外如果遇到单词则返回 true，结果会超时，因为要同时维护的过多节点，代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        m_head = new TrieNode();
        for (const std::string& word: words) {
            insertWord(word);
        }
        m_candidates.push(m_head);
    }

    bool query(char letter) {
        int index = letter - 'a';
        bool found_word = false;
        int count = m_candidates.size();
        m_candidates.push(m_head);
        while (count > 0) {
            TrieNode* candidate = m_candidates.front();
            m_candidates.pop();
            count--;
            if (!candidate->next_level[index]) continue;
            candidate = candidate->next_level[index];
            if (candidate->is_word) found_word = true;
            m_candidates.push(candidate);
        }
        return found_word;
    }

private:
    struct TrieNode {
        std::vector<TrieNode*> next_level;
        bool is_word;
        TrieNode(): next_level(26), is_word(false) {}
    };

    TrieNode* m_head;
    std::queue<TrieNode*> m_candidates;

    void insertWord(const std::string& word) {
        TrieNode* current = m_head;
        for (int i = 0; i < word.length(); i++) {
            int index = word[i] - 'a';
            if (!current->next_level[index]) {
                current->next_level[index] = new TrieNode();
            }
            current = current->next_level[index];
        }
        current->is_word = true;
    }

};
  • 时间复杂度：Solution: O(n)， Query: O(N) 最坏情况是所有节点都在候选队列中（类似于 aaaaa... 的情况）
  • 空间复杂度：O(N)

方法二

方法一的弊端在于候选节点太多，如果我们反向存单词的话（从尾到头存入）。然后对于所有查询字符都存在一个字符串里，这样就变成了常规的字典树查询操作，另外由于字典树中最长存在的单词长度为 k， 所以我们存的字符串超过 k 时还可以进行裁剪，进一步优化所需空间，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        m_head = new TrieNode();
        for (const std::string& word: words) {
            insertWord(word);
        }
        current_string = "";
    }

    bool query(char letter) {
        current_string += letter;
        TrieNode* curr = m_head;
        for (int i = current_string.length() - 1; i >= 0; i--) {
            if (!curr->next_level[current_string[i] - 'a']) return false;
            curr = curr->next_level[current_string[i] - 'a'];
            if (curr->is_word) return true;
        }
        return false;
    }

private:
    struct TrieNode {
        std::vector<TrieNode*> next_level;
        bool is_word;
        TrieNode(): next_level(26), is_word(false) {}
    };

    TrieNode* m_head;
    std::string current_string;

    void insertWord(const std::string& word) {
        TrieNode* current = m_head;
        for (int i = word.length() - 1; i >= 0; i--) {
            int index = word[i] - 'a';
            if (!current->next_level[index]) {
                current->next_level[index] = new TrieNode();
            }
            current = current->next_level[index];
        }
        current->is_word = true;
    }

};
  • 时间复杂度：Solution: O(n)， Query: O(k) k 为单词最大长度
  • 空间复杂度：O(N)

推荐文章