C++ | Dfs | Deconstructor | TC - O(n) to add & O(26^n) to search
\nclass TrieNode{\npublic:\n    TrieNode* children[26] = {NULL};\n    int isWord = false;\n};\n\nclass WordDictionary {\nprivate:\n    TrieNode* root;\npublic:\
```\nclass TrieNode{\npublic:\n    TrieNode* children[26] = {NULL};\n    int isWord = false;\n};\n\nclass WordDictionary {\nprivate:\n    TrieNode* root;\npublic:\n    WordDictionary() {\n        root = new TrieNode();\n    }\n    void addWord(string word) {   //O(N) TIME\n        auto cur = root;\n        for(auto &w : word){\n            int k = w - \'a\';\n            if(cur->children[k]==NULL){\n                cur->children[k] = new TrieNode;\n            }\n            cur = cur->children[k];\n        }\n        cur->isWord = true;\n    }\n    bool searchWord(string &word, int ind, TrieNode* cur){  //O(26^N) TIME\n        for(int i = ind; i < word.size(); i++){\n            if(word[i]==\'.\'){\n                for(int k = 0 ; k < 26; k++){\n                    auto temp = cur->children[k];\n                    if(temp!=NULL && searchWord(word, i+1, temp))\n                            return true;\n                }   \n                return false;\n            }else{\n                int k = word[i] - \'a\';\n                cur = cur->children[k];   \n                if(cur == NULL) return false;\n            }\n        }\n        return cur->isWord;\n    }\n    bool search(string word) {\n        return searchWord(word, 0, root);\n    }\n    \n    //Deconstructor\n    ~WordDictionary(){                      \n        clear_nodes(root);\n    }\n    void clear_nodes(TrieNode* root) \n    {\n        for(int i = 0; i<26; i++)\n            if(root->children[i] != NULL)\n                clear_nodes(root->children[i]);\n        delete root;\n    }\n};\n```
['Backtracking', 'Depth-First Search', 'Trie', 'Recursion', 'C']