208. Implement Trie (Prefix Tree)
148ms 31.89%
字典树的构建,搜索,插入操作。维护一个26大小的数组即可,
- 注意每次插入后,要把末尾节点的end置位
为什么这样不行: 因为private中只是声明了变量,并没有为其分配空间,我们需要在构造函数中
Trie() {root=new node();}
class node{
public:
node*next[26]={};
bool end=false;
};
class Trie {
public:
/** Initialize your data structure here. */
Trie() {
for(int i=0;i<26;i++){
root->next[i]=nullptr;
}
}
/** Inserts a word into the trie. */
void insert(string word) {
node* tmp=root;
for(int i=0;i<word.size();i++){
tmp->next[word[i]-'a']=new node();
tmp=tmp->next[word[i]-'a'];
}
tmp->end=true;
return;
}
/** Returns if the word is in the trie. */
bool search(string word) {
node*tmp=root;
for(int i=0;i<word.size();i++){
if(tmp->next[word[i]-'a']==NULL) return false;
tmp=tmp->next[word[i]-'a'];
}
return tmp->end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
node*tmp=root;
for(int i=0;i<prefix.size();i++){
if(tmp->next[prefix[i]-'a']==NULL) return false;
tmp=tmp->next[prefix[i]-'a'];
}
return true;
}
private:
node *root;
};
AC代码
class Trie {
public:
/** Initialize your data structure here. */
Trie() {
}
/** Inserts a word into the trie. */
void insert(string word) {
Trie* tmp=this;
for(int i=0;i<word.size();i++){
if(tmp->next[word[i]-'a']==NULL)
tmp->next[word[i]-'a']=new Trie();
tmp=tmp->next[word[i]-'a'];
}
tmp->end=true;
return;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Trie*tmp=this;
for(int i=0;i<word.size();i++){
if(tmp->next[word[i]-'a']==NULL) return false;
tmp=tmp->next[word[i]-'a'];
}
return tmp->end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
Trie*tmp=this;
for(int i=0;i<prefix.size();i++){
if(tmp->next[prefix[i]-'a']==NULL) return false;
tmp=tmp->next[prefix[i]-'a'];
}
return true;
}
private:
Trie *next[26]={};
bool end=false;
};
/**
* 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);
*/