class Trie {
public:
/** Initialize your data structure here. */
struct NODE {
char l;
bool wordFinish;
struct NODE* next[26];
};
struct NODE* root;
Trie() {
root = new struct NODE();
}
/** Inserts a word into the trie. */
void insert(string word) {
struct NODE* curr = root;
for (int i = 0; i < word.size(); i++) {
char c = word[i];
if (curr->next[c - 'a'] == NULL) {
curr->next[c - 'a'] = new struct NODE();
}
curr = curr->next[c - 'a'];
curr->l = c;
if (i == word.size() - 1) {
curr->wordFinish = true;
}
}
}
/** Returns if the word is in the trie. */
bool search(string word) {
struct NODE* curr = root;
for (int i = 0; i < word.size(); i++) {
char c = word[i];
curr = curr->next[c - 'a'];
if (curr == NULL) return false;
else {
if (i == word.size() - 1 && curr->wordFinish == true) {
return true;
}
else if(i == word.size() - 1){
return false;
}
}
}
return false;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
struct NODE* curr = root;
for (int i = 0; i < prefix.size(); i++) {
char c = prefix[i];
curr = curr->next[c - 'a'];
if (curr == NULL) return false;
else {
if (i == prefix.size() - 1 ) {
return true;
}
}
}
return false;
}
};
| 
