LeetCode 208. 实现 Trie (前缀树)
原题链接
中等
作者:
我是java同学
,
2023-10-03 21:52:59
,
所有人可见
,
阅读 66
class Trie {
public:
struct Node {
bool is_end;
Node *son[26];
Node () {
is_end = false;
for (int i = 0; i < 26; i ++ )
son[i] = NULL;
}
}*root;
Trie() {
root = new Node();
}
void insert(string word) {
auto p = root;
for (auto c: word) {
int u = c - 'a';
if (!p->son[u]) p->son[u] = new Node();
p = p->son[u];
}
p->is_end = true;
}
bool search(string word) {
auto p = root;
for (auto c: word) {
auto u = c - 'a';
if (!p->son[u]) return false;
p = p->son[u];
}
return p->is_end;
}
bool startsWith(string word) {
auto p = root;
for (auto c: word) {
auto u = c - 'a';
if (!p->son[u]) return false;
p = p->son[u];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/