const int ALPHABETS = 26;
class trieNode{
char ch;
public:
trieNode * children[ALPHABETS];
bool isTerminal;
trieNode(char ch) : ch(ch), isTerminal(false) {
for(int i=0;i<ALPHABETS;++i) children[i] = nullptr;
}
};
class Trie {
public:
trieNode * root;
/** Initialize your data structure here. */
Trie() {
root = new trieNode('\0');
}
void insertUtil(trieNode*, string);
bool searchUtil(trieNode*, string);
bool startsWithUtil(trieNode*, string);
/** Inserts a word into the trie. */
void insert(string word) {
insertUtil(root, word);
}
/** Returns if the word is in the trie. */
bool search(string word) {
return searchUtil(root, word);
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return startsWithUtil(root, prefix);
}
};
void Trie :: insertUtil(trieNode* root, string str){
if(str.length() == 0){
root->isTerminal = true;
return;
}else{
int index = str[0] - 'a';
trieNode* child = nullptr;
if(root->children[index] != nullptr) child = root->children[index];
else{
child = new trieNode(str[0]);
root->children[index] = child;
}
insertUtil(child, str.substr(1));
}
}
bool Trie :: searchUtil(trieNode* root, string str){
if(str.length() == 0) return root->isTerminal;
else{
int index = str[0] - 'a';
trieNode* child = nullptr;
if(root->children[index] != nullptr) child = root->children[index];
else return false;
return searchUtil(child, str.substr(1));
}
}
bool Trie :: startsWithUtil(trieNode* root, string str){
if(str.length() == 0) return true;
else{
int index = str[0] - 'a';
trieNode * child = nullptr;
if(root->children[index] != nullptr) child = root->children[index];
else return false;
return startsWithUtil(child, str.substr(1));
}
}