11
05/2015
[LeetCode] Implement Trie (Prefix Tree)
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.
解题思路：
前缀树。由于值设定为在a-z之间，我们可以假设是一棵26叉树。注意，每个节点还需要加入一个标记，表明从根到这个节点的路径组成的序列是否为单词。
class TrieNode {
public:
// Initialize your data structure here.
TrieNode() {
this->bWord=false;
for(int i=0; i<26; i++){
this->son[i] = NULL;
}
}
TrieNode* getSon(char c){
return this->son[c-'a'];
}
void setSon(int i, TrieNode* node){
this->son[i] = node;
}
bool isWord(){
return this->bWord;
}
void markAsWord(){
this->bWord = true;
}
private:
bool bWord;
TrieNode* son[26];
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
void insert(string s) {
int len = s.length();
TrieNode* parent = root, *node;
for(int i=0;i<len; i++){
node = parent->getSon(s[i]);
if(node == NULL){
node=new TrieNode();
parent->setSon(s[i] - 'a', node);
}
parent = node;
}
parent->markAsWord();
}
// Returns if the word is in the trie.
bool search(string key) {
int len = key.length();
TrieNode* node = root;
for(int i=0; i<len; i++){
node = node->getSon(key[i]);
if(node==NULL){
return false;
}
}
return node->isWord();
}
// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
int len = prefix.length();
TrieNode* node = root;
for(int i=0; i<len; i++){
node = node->getSon(prefix[i]);
if(node==NULL){
return false;
}
}
return true;
}
private:
TrieNode* root;
};
// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");
0 条评论