Implement Trie (Prefix Tree)- Medium - L
Published:
Question
- https://leetcode.com/problems/implement-trie-prefix-tree/
Trie (we pronounce “try”) or prefix tree is a tree data structure used to retrieve a key in a strings dataset. There are various applications of this very efficient data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() initializes the trie object.
void insert(String word) inserts the string word to the trie.
boolean search(String word) returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
Approach
- Standard approach for struct
Solution
class Trie {
public:
/** Initialize your data structure here. */
struct TrieNode {
bool isEnd;
TrieNode* arr[26];
};
TrieNode* trie = NULL;
Trie() {
trie = new TrieNode();
trie->isEnd=true;
for(int i=0;i<26;i++){
trie->arr[i]=NULL;
}
}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode* t = trie;
for(int i=0;i<word.size();i++){
if(trie->arr[word[i]-'a']==NULL){
TrieNode* t1 = new TrieNode();
for(int i=0;i<26;i++){
t1->arr[i]==NULL;
}
trie->arr[word[i]-'a']=t1;
}
trie=trie->arr[word[i]-'a'];
}
trie->isEnd=true;
trie=t;
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode* t = trie;
for(int i=0;i<word.size();i++){
if(t->arr[word[i]-'a']==NULL){
return false;
}
t=t->arr[word[i]-'a'];
}
if(t->isEnd==false){
return false;
}
return true;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
TrieNode* t = trie;
for(int i=0;i<prefix.size();i++){
if(t->arr[prefix[i]-'a']==NULL){
return false;
}
t=t->arr[prefix[i]-'a'];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/