LeetCode 1032. 字符流
原题链接
困难
作者:
我是java同学
,
2023-10-16 16:50:16
,
所有人可见
,
阅读 48
class StreamChecker {
public:
string str;
struct Node {
bool is_end;
Node* son[26];
Node() {
is_end = false;
for (int i = 0; i < 26; i ++ )
son[i] = NULL;
}
}* root;
void insert(string s) {
auto p = root;
for (auto c: s) {
int u = c - 'a';
if (!p->son[u]) p->son[u] = new Node();
p = p->son[u];
}
p->is_end = true;
}
bool query(string s) {
auto p = root;
for (auto c: s) {
int u = c - 'a';
if (!p->son[u]) return false;
p = p->son[u];
}
return p->is_end;
}
StreamChecker(vector<string>& words) {
root = new Node();
for (auto word: words) {
reverse(word.begin(), word.end());
insert(word);
}
}
bool query(char letter) {
auto p = root;
str += letter;
for (int i = str.size() - 1; i >= 0; i -- ) {
int u = str[i] - 'a';
if (!p->son[u]) return false;
p = p->son[u];
if (p->is_end) return true;
}
return false;
}
};
/**
* Your StreamChecker object will be instantiated and called as such:
* StreamChecker* obj = new StreamChecker(words);
* bool param_1 = obj->query(letter);
*/