class WordDictionary {
public:
    struct TrieNode
    {
        TrieNode *child[26]={};
        bool w=0;
    };
    TrieNode *root=new TrieNode();
    WordDictionary() {
        
    }
    
    void addWord(string word) {
        TrieNode *it=root;
        for(int i=0; i<word.size(); i++)
        {
            int ind=word[i]-'a';
            if(!it->child[ind]) it->child[ind]=new TrieNode();
            it=it->child[ind];
        }
        it->w=1;
    }
    bool search(string word)
    {
        return search(root, word);
    }
    
    bool search(TrieNode *it, string word) {
        for(int i=0; i<word.size() && it; i++)
        {
            if(word[i]!='.')
            {
                int ind=word[i]-'a';
                if(!it->child[ind]) return false;
                it=it->child[ind];   
            }
            else
            {
                string s=word.substr(i+1);
                TrieNode *tmp=it;
                for(int j=0; j<26; j++)
                {
                    it=tmp->child[j];
                    if(search(it, s)) return true;
                }
            }
        }
        return it && it->w; //covers the case when the it is null, and that happens only when going from . to any other character which doesn't exist.
    }
};

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