class TrieNode {
public:
// Initialize your data structure here.
TrieNode() {
words=;
prefixs=;
for(int i=;i<;i++)
edges[i]=NULL;
}
int words;
int prefixs;
TrieNode* edges[];
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
void insert(string word) {
insertHelper(root,word,);
}
// Returns if the word is in the trie.
bool search(string word) {
return searchHelper(root,word,)!=;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
return startsWithHelper(root,prefix,)!=;
}
void insertHelper(TrieNode * node,string &word,int pos) {
if(pos==word.size())
{
node->words++;
node->prefixs++;
}
else
{
node->prefixs++;
int char_code=word[pos]-'a';
if(node->edges[char_code]==NULL)
node->edges[char_code]=new TrieNode();
insertHelper(node->edges[char_code],word,pos+);
}
}
int searchHelper(TrieNode * node,string &word,int pos)
{
int char_code=word[pos]-'a';
if(pos==word.size())
return node->words;
else if(node->edges[char_code]==NULL)
return ;
else
return searchHelper(node->edges[char_code],word,pos+);
}
int startsWithHelper(TrieNode * node,string &word,int pos)
{
int char_code=word[pos]-'a';
if(pos==word.size())
return node->prefixs;
else if(node->edges[char_code]==NULL)
return ;
else
return startsWithHelper(node->edges[char_code],word,pos+);
}
private:
TrieNode* root;
};
/**
* 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);
*/补充一个python的实现：
class TrieNode:
def __init__(self):
self.words = 0
self.prefixs = 0
self.edges = [None] * 26 class Trie:
def __init__(self):
self.root = TrieNode() def insert(self,word):
self.insertHelper(self.root,word,0) def search(self,word):
return self.searchHelper(self.root,word,0) != 0 def startsWith(self,prefix):
return self.startsWithHelper(self.root,prefix,0) != 0 def insertHelper(self,node,word,pos):
if pos == len(word):
node.words += 1
node.prefixs += 1
else:
node.prefixs += 1
char_code = ord(word[pos]) - 97
if node.edges[char_code] == None:
node.edges[char_code] = TrieNode()
self.insertHelper(node.edges[char_code],word,pos+1) def searchHelper(self,node,word,pos):
if pos == len(word):
return node.words
else:
char_code = ord(word[pos]) - 97
if node.edges[char_code] == None:
return 0
else:
return self.searchHelper(node.edges[char_code],word,pos+1) def startsWithHelper(self,node,word,pos):
if pos == len(word):
return node.prefixs
else:
char_code = ord(word[pos]) - 97
if node.edges[char_code] == None:
return 0
else:
return self.startsWithHelper(node.edges[char_code],word,pos+1)