Implement a trie with insert
, search
, and startsWith
methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z
.
class TrieNode {
public:
// Initialize your data structure here.
bool isWord;
unordered_map<char, TrieNode*> alpha;
TrieNode():isWord(false) {}
};class Trie {
public:
Trie() {
root = new TrieNode();
} // Inserts a word into the trie.
void insert(string word) {
TrieNode *p = root;
int l = word.length(), i;
for(i = ; i < l; i++)
{
if(p->alpha.find(word[i]) == p->alpha.end())
{
TrieNode *t = new TrieNode();
p->alpha[word[i]] = t;
}
p = p->alpha[word[i]];
}
p->isWord = true;
} // Returns if the word is in the trie.
bool search(string word) {
TrieNode *p = root;
int l = word.length(), i;
for(i = ; i < l; i++)
{
if(p->alpha.find(word[i]) == p->alpha.end())
return false;
p = p->alpha[word[i]];
}
return p->isWord;
} // Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode *p = root;
int l = prefix.length(), i;
for(i = ; i < l; i++)
{
if(p->alpha.find(prefix[i]) == p->alpha.end())
return false;
p = p->alpha[prefix[i]];
}
return true;
}private:
TrieNode* root;
};// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");