class TrieNode {
public:
const static int NR_FANOUT = ;
TrieNode* child[NR_FANOUT];
int count;
// Initialize your data structure here.
TrieNode() {
for (int i=; i<NR_FANOUT; i++) {
child[i] = NULL;
}
count = ;
}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
void insert(string s) {
insert(s, , root);
}
// Returns if the word is in the trie.
bool search(string key) {
return search(key, , root) != NULL;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
return search_prefix(prefix, , root) != NULL;
}
private:
TrieNode* insert(string& s, int pos, TrieNode* current) {
int len = s.size();
if (pos > len) {
return NULL;
}
if (current == NULL) {
current = new TrieNode();
}
if (pos == len) {
current->count++;
return current;
}
int idx = s[pos] - 'a';
current->child[idx] = insert(s, pos + , current->child[idx]);
return current;
}
TrieNode* search(string& s, int pos, TrieNode* current) {
if (current == NULL) {
return NULL;
}
int len = s.size();
if (pos > len) {
return NULL;
} else if (pos == len && current->count) {
return current;
}
return search(s, pos + , current->child[s[pos] - 'a']);
}
TrieNode* search_prefix(string& s, int pos, TrieNode* current) {
if (current == NULL) {
return NULL;
}
int len = s.size();
if (pos >= len) {
return current;
}
return search_prefix(s, pos + , current->child[s[pos] - 'a']);
}
private:
TrieNode* root;
};
mplement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.