LeetCode 208. 实现 Trie (前缀树)
原题链接
中等
作者:
ShineShaye
,
2022-12-13 14:16:00
,
所有人可见
,
阅读 129
C++ 代码
class Trie {
public:
// 用一个结构体存储trie树的每个节点
// 因为每个字母的后面一个位置可能有26种情况(26个字母),初始化26个空指针
struct Node{
bool is_end; // 每个节点有一个标志,是否有完整单词在该点结尾
Node* son[26];
Node(){
is_end = false;
memset(son, NULL, sizeof(son));
}
};
// 新建全局变量,指向根节点的指针
Node* root;
Trie() {
// 初始化根节点
root = new Node();
}
// 插入一个单词
void insert(string word) {
// 从根节点开始向下建树
auto tmp = root;
for(auto x : word){
// 计算每个字母对应的指针下标
int idx = x - 'a';
// 如果不存在当前字母的节点,创建新节点接在后面
if(!tmp->son[idx]) tmp->son[idx] = new Node();
// 继续向下走
tmp = tmp->son[idx];
}
// 对于单词的最后一个字母,标记一下
tmp->is_end = true;
}
bool search(string word) {
auto tmp = root;
for(auto x : word){
int idx = x - 'a';
// 查找的当前单词位没有节点,说明不存在单词
if(!tmp->son[idx]) return false;
tmp = tmp->son[idx];
}
// 是否有单词解为标志
return tmp->is_end;
}
bool startsWith(string prefix) {
auto tmp = root;
for(auto x : prefix){
int idx = x - 'a';
if(!tmp->son[idx]) return false;
tmp = tmp->son[idx];
}
// 求前缀,那么只要树有节点到这里,说明一定有前缀
return true;
}
};