0%

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

题目描述

题目链接: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)