Trie Tree

class TrieNode {
public:
    
    TrieNode() {
        for(int i = 0; i < 26; i++)
            next[i] = NULL;
        isString = false;
    }
    TrieNode *next[26];
    bool isString;
};
 
class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
 
    // Inserts a word into the trie.
    void (string word) {
        TrieNode *p = root;
        for(int i = 0; i < word.size(); i++){
            if(p->next[word[i]-'a'] == NULL){
                p->next[word[i]-'a'] = new TrieNode();
            }
            p = p->next[word[i]-'a'];
        }
        p->isString = true;
    }
 
    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode *p = root;
        for(int i = 0; i < word.size(); i++){
            if(p == NULL) return false;
            p = p->next[word[i]-'a'];
        }
        if(p == NULL || p->isString == 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 *p = root;
        for(int i = 0; i < prefix.size(); i++) {
            p = p->next[prefix[i]-'a'];
            if(p == NULL) return false;
        }
        return true;
    }
 
private:
    TrieNode* root;
};

class TrieNode {
public:
    bool isString;
    TrieNode *next[26];
    TrieNode () {
        for (int i = 0; i < 26; i++) next[i] = NULL;
        isString = false;
    }
};
class WordDictionary {
public:
    
    // Adds a word into the data structure.
    WordDictionary () {
        root = new TrieNode();
    }
    
    void addWord(string word) {
        // Write your code here
        TrieNode *p = root;
        for (char c : word) {
            if (!p->next[c-'a']) {
                p->next[c-'a'] = new TrieNode();
            }
            p = p->next[c-'a'];
        }
        p->isString = true;
    }
    
    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        // Write your code here
        TrieNode *p = root;
        bool res = helper(word, 0, p);
        return res;
    }
    
    bool helper(string word, int pos, TrieNode *p) {
        if (!p) return false;
        if (pos >= word.size()) {
            if (p->isString) return true;
            else return false;
        }
        if (word[pos] != '.') return helper(word, pos+1, p->next[word[pos]-'a']);
        else {
            bool res = false;
            for (int j = 0; j < 26; j++) {
                if (p->next[j] != NULL) {
                    res = res || helper(word, pos+1, p->next[j]);
                }
            }
            return res;
        }
    }
    
private:
    TrieNode *root;
};