原题描述
Implement a trie with insert, search, and startsWith methods.
Trie树的分析和实现
本题为了实现方便采用静态分配法，详细的Trie树可以见我的另一篇博客
C++代码
class TrieNode {
public:
// Initialize your data structure here.
TrieNode* next[26];
bool valid;
TrieNode() {
memset(next, NULL, sizeof(next));
valid = false;
}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
void insert(string word) {
if (word.length() <= 0) {
return;
}
int len = word.length();
TrieNode* p = root;
for (int i = 0; i < len; i++) {
if (p->next[word[i] - 'a'] == NULL) {
p->next[word[i] - 'a'] = new TrieNode();
p = p->next[word[i] - 'a'];
}
else {
p = p->next[word[i] - 'a'];
}
}
p->valid = true;
}
// Returns if the word is in the trie.
bool search(string word) {
if (word.length() <= 0) {
return false;
}
int len = word.length();
TrieNode* p = root;
for (int i = 0; i < len; i++) {
if (p->next[word[i] - 'a'] != NULL) {
p = p->next[word[i] - 'a'];
}
else {
return false;
}
}
if (p->valid) {
return true;
}
else {
return false;
}
}
// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
if (prefix.length() <= 0) {
return false;
}
int len = prefix.length();
TrieNode* p = root;
for (int i = 0; i < len; i++) {
if (p->next[prefix[i] - 'a'] == NULL) {
return false;
}
else {
p = p->next[prefix[i] - 'a'];
}
}
return true;
}
private:
TrieNode* root;
};
// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");