WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

class WordDictionary {
public:
    /** Initialize your data structure here. */
    
    struct TrieNode {
        bool isEnd;
        TrieNode* arr[26];
    };
    
    TrieNode* trie = NULL;
    
    WordDictionary() {
        trie = new TrieNode();
        trie->isEnd=true;
        for(int i=0;i<26;i++){
            trie->arr[i]=NULL;
        }
    }
    
    void addWord(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;
    }
    
    void searchUtil(string word, int i, TrieNode* t, bool &ans) {
        int n = word.size();
        if (t==NULL) {
            return;
        }
        if (i>=n) {
            if(t->isEnd==false){
                ans = false;
                return;
            } 
            ans = true;
            return;
        }
        cout<<word<<endl;
        cout<<i<<" "<<n<<" "<<word[i]<<endl;
        if(word[i]=='.') {
            for(int j=0; j<26; j++) {
                cout<<i<<":"<<j<<":"<<(t->arr[j]!=NULL)<<endl;
                if(t->arr[j]!=NULL && ans==false) {
                    cout<<j<<endl;
                    TrieNode* t1 = t->arr[j];
                    searchUtil(word, i+1, t1, ans);
                }
            }
            return;
        } else if(t->arr[word[i]-'a']==NULL) {
            ans = false;
            return;
        } else {
            TrieNode* t1 =t->arr[word[i]-'a'];   
            cout<<"hi"<<endl;
            searchUtil(word, i+1, t1, ans);
        }
    }
    
    bool search(string word) {
        TrieNode* t = trie;
        bool ans = false;
        searchUtil(word, 0, t, ans);
        return ans;
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */