Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
Just code
const int N = 26;
class TrieNode {
public:
// Initialize your data structure here.
TrieNode* children[N];
bool iskey;
TrieNode() {
for(size_t i=0; i<N; i++){
children[i] = NULL;
}
iskey = false;
}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
void insert(string word) {
TrieNode *p = root;
for(size_t i=0; i<word.size(); i++){
int ci = word[i]-'a';
if(!p){
p = new TrieNode();
}
if(p->children[ci] == NULL){
p->children[ci] = new TrieNode();
}
p = p->children[ci];
}
p->iskey = true;
}
bool search(string word) {
TrieNode *p = root;
for(size_t i=0; i<word.size(); i++){
int ci = word[i]-'a';
if(!p || p->children[ci] == NULL){
return false;
}
p = p->children[ci];
}
return p && p->iskey;
}
bool startsWith(string prefix) {
TrieNode *p = root;
for(size_t i=0; i<prefix.size(); i++){
int ci = prefix[i]-'a';
if(!p || p->children[ci] == NULL){
return false;
}
p = p->children[ci];
}
return true;
}
private:
TrieNode* root;
};
// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");
留下评论