Implement a trie with insert, search, and startsWith methods.
Notice
You may assume that all inputs are consist of lowercase letters a-z.
Have you met this question in a real interview?
Yes
Example
insert("lintcode")
search("code")
>
>
>
false
startsWith("lint")
>
>
>
true
startsWith("linterror")
>
>
>
false
insert("linterror")
search("lintcode)
>
>
>
true
startsWith("linterror")
>
>
>
true
extra node to save if it's a string flag, easy to code
/**
* 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.
TrieNode\(\) {
for \(int i = 0; i < 26; ++i\) {
next\[i\] = NULL;
}
IsEnd = false;
}
TrieNode\* next\[26\];
bool IsEnd;
};
class Trie {
public:
Trie\(\) {
root = new TrieNode\(\);
}
// Inserts a word into the trie.
void insert\(string word\) {
TrieNode\* p = root;
for \(int i = 0; i < word.length\(\); ++i\) {
int index = word\[i\] - 'a';
if \(p->next\[index\] == NULL\) {
p->next\[index\] = new TrieNode\(\);
}
p = p->next\[index\];
}
p->IsEnd = true;
}
// Returns if the word is in the trie.
bool search\(string word\) {
TrieNode\* p = root;
for \(int i = 0; i < word.length\(\); ++i\) {
int index = word\[i\] - 'a';
if \(p->next\[index\] == NULL\) {
return false;
}
p = p->next\[index\];
}
return p->IsEnd;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith\(string prefix\) {
TrieNode\* p = root;
for \(int i = 0; i < prefix.length\(\); ++i\) {
int index = prefix\[i\] - 'a';
if \(p->next\[index\] == NULL\) {
return false;
}
p = p->next\[index\];
}
return true;
}
private:
TrieNode\* root;
};