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

题目解析

题目的意思就是通过不断的query(c)来添加历史记录,然后看是不是历史记录里包括给定的词。

方法

解法关键在于如何快速的找到这些词,这里使用前缀树来使每次查找的时间复杂度在O(logW), W是最长的单词,题目里W最大是200,最多查询40000次,故不会超时

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
51
class StreamChecker {
public:
struct TreeNode {
TreeNode *left;
TreeNode *right;
TreeNode *letters[26];
bool is_word = false;
};
StreamChecker(vector<string> &words) {
trie = new TreeNode();
for (auto &word : words) {
reverse(word.begin(), word.end());
build(trie, word);
}
}

bool query(char letter) {
history.push_back(letter);
return search(trie, history.size() - 1);
}

void build(TreeNode *root, string &word) {
for (int i = 0; i < word.size(); i++) {
if (!root->letters[word[i] - 'a']) {
root->letters[word[i] - 'a'] = new TreeNode();
}
if (i == word.size() - 1) {
root->letters[word[i] - 'a']->is_word = true;
}
root = root->letters[word[i] - 'a'];
}
}

bool search(TreeNode *trie, int index) {
for (int i = history.size() - 1; i >= 0; i--) {
char c = history[i];
TreeNode *next = trie->letters[c - 'a'];
if (!next) {
return false;
} else if (next->is_word) {
return true;
}
trie = next;
}
return false;
}

private:
vector<char> history;
TreeNode *trie;
};