數(shù)據(jù)結(jié)構(gòu)之Trie樹
Trie樹：應(yīng)用于統(tǒng)計和排序
實現(xiàn)一個 Trie扰魂，包含 insert, search, 和 startsWith 這三個方法麦乞。
注意事項
你可以假設(shè)所有的輸入都是小寫字母a-z。
您在真實的面試中是否遇到過這個題劝评？ Yes
樣例
insert("lintcode")
search("code") // return false
startsWith("lint") // return true
startsWith("linterror") // return false
insert("linterror")
search("lintcode) // return true
startsWith("linterror") // return true
/**
* Your Trie object will be instantiated and called as such:
* Trie trie;
* trie.insert("lintcode");
* trie.search("lint"); will return false
* trie.startsWith("lint"); will return true
*/
class TrieNode {
public:
// Initialize your data structure here.
bool isWord = false;
TrieNode *child[26];
TrieNode() {
memset(child, 0, sizeof(child));
}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
void insert(string word) {
TrieNode *pt = root;
int len = word.size();
for(int i = 0;i < len;i++) {
int index = word[i] - 'a';
if(pt->child[index] == NULL) pt->child[index] = new TrieNode();
pt = pt->child[index];
}
pt->isWord = true;
}
// Returns if the word is in the trie.
bool search(string word) {
int len = word.size();
TrieNode* pt = root;
for(int i = 0;i < len;i++) {
int index = word[i] - 'a';
if(pt->child[index] == NULL) return false;
else {
pt = pt->child[index];
}
}
return pt->isWord;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
int len = prefix.size();
TrieNode* pt = root;
for(int i = 0;i < len;i++) {
int index = prefix[i] - 'a';
if(pt->child[index] == NULL) return false;
else {
pt = pt->child[index];
}
}
return true;
}
private:
TrieNode* root;
};
