leetcode@ [208] Implement Trie (Prefix Tree)

时间:2021-04-27 23:52:51

Trie 树模板

https://leetcode.com/problems/implement-trie-prefix-tree/

class TrieNode {
public:
char var;
bool isWord;
TrieNode *next[];
TrieNode() {
var = ;
this->isWord = false;
for(auto &c : next) c = NULL;
}
TrieNode(char c) {
var = c;
this->isWord = false;
for(auto &c : next) c = NULL;
}
}; class Trie {
public:
Trie() {
root = new TrieNode();
} // Inserts a word into the trie.
void insert(string word) {
TrieNode *p = root;
for(auto &a : word) {
int idx = a - 'a';
if(!p->next[idx]) p->next[idx] = new TrieNode();
p = p->next[idx];
}
p->isWord = true;
} // Returns if the word is in the trie.
bool search(string word) {
TrieNode *p = root;
for(auto &a : word) {
int idx = a - 'a';
if(!p->next[idx]) return false;
p = p->next[idx];
}
return p->isWord;
} // Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode *p = root;
for(auto &a : prefix) {
int idx = a - 'a';
if(!p->next[idx]) return false;
p = p->next[idx];
}
return true;
} private:
TrieNode* root;
}; // Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");