实现思路是每个结点保存一个26个指针数组,在插入的时候建立前后关系,查询完整单词依赖is_word,而查询前缀只要单词长度查完,没有出现NULL即匹配,完整代码如下(包含析构函数):
class TrieNode {
public:
// Initialize your data structure here.
bool is_word;
TrieNode *children[26];
TrieNode() {
is_word = false;
for (int i = 0; i < 26; i++)
children[i] = NULL;
}
};
class Trie {
public:
/** Initialize your data structure here. */
Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
void insert(string word) {
int len = word.length();
TrieNode * cur = root;
for(int i = 0;i < len;i++){
int k = word[i] - 'a';
if(cur->children[k] == NULL){
cur->children[k] = new TrieNode();
}
cur = cur->children[k];
}
//设置完整单词标志
cur->is_word = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode * cur = root;
int len = word.length();
for(int i = 0;i < len ;i++){
int k = word[i] - 'a';
if(cur->children[k] == NULL)
return false;
cur = cur->children[k];
}
if(cur->is_word){
return true;
}
return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
TrieNode * cur = root;
int len = prefix.length();
for(int i = 0;i < len ;i++){
int k = prefix[i] - 'a';
if(cur->children[k] == NULL)
return false;
cur = cur->children[k];
}
return true;
}
~Trie() {
clear(root);
}
private:
TrieNode * root;
void clear(TrieNode * cur)
{
for(int i = 0;i < 26;i++)
{
if(cur->children[i]){
clear(cur->children[i]);
}
}
delete cur;
}
};
/**
* 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);
*/
运行结果:
Runtime: 84 ms, faster than 67.60% of C++ online submissions for Implement Trie (Prefix Tree).
Memory Usage: 45.4 MB, less than 40.73% of C++ online submissions for Implement Trie (Prefix Tree).