[C++] Trie + DFS solution. [Detailed Explanation]
\n/*\n    https://leetcode.com/problems/design-add-and-search-words-data-structure/submissions/\n    \n    Idea is to use a Trie for adding the words. Now since
```\n/*\n    https://leetcode.com/problems/design-add-and-search-words-data-structure/submissions/\n    \n    Idea is to use a Trie for adding the words. Now since we have a special char \'.\'\n    which can match any single char, so we need to look into all possible cmb from that point.\n    We can use DFS for searching, when we get \'.\' we do DFS for all the leaves nodes for\n    the current level of Trie and check any of the DFS is able to find the complete pattern\n    sequence.\n*/\n\nclass WordDictionary {\n    struct TrieNode {\n        unordered_map<char, TrieNode*> leaves;\n        bool is_string = false;\n    };\n    \n    TrieNode *root_ = nullptr;\npublic:\n    /** Initialize your data structure here. */\n    WordDictionary() {\n        root_ = new TrieNode();\n    }\n    \n    /** Adds a word into the data structure. */\n    // TC: O(L)\n    void addWord(string word) {\n        TrieNode *root = root_;\n        \n        for(char &c: word) {\n            // Create a node if it doesn\'t exists for current char\n            if(root->leaves.count(c) == 0)\n                root->leaves[c] = new TrieNode();\n            root = root->leaves[c];\n        }\n        // mark the end of string\n        root->is_string = true;\n    }\n    \n    // Searches for a word in Trie\n    // TC: O(n * L), L: length of longest word\n    // Worst case: when all the chars are . and all words in Trie are of same length\n    bool searchWord(int idx, TrieNode *root, string &word) {\n        // all the chars coevered, check if the current node marks\n        // string end\n        if(idx == word.size())\n            return root->is_string;\n        \n        // if . char, match with all available chars at the current level\n        if(word[idx] == \'.\') {\n            for(auto it = root->leaves.begin(); it != root->leaves.end(); it++) {\n                if(searchWord(idx+1, it->second, word))\n                    return true;\n            }\n        }\n        else if(root->leaves.count(word[idx]))\n                return searchWord(idx+1, root->leaves[word[idx]], word);\n        \n        return false;\n    }\n    \n    /** Returns if the word is in the data structure. A word could contain the dot character \'.\' to represent any one letter. */\n    bool search(string word) {\n        return searchWord(0, root_, word);\n    }\n};\n\n/**\n * Your WordDictionary object will be instantiated and called as such:\n * WordDictionary* obj = new WordDictionary();\n * obj->addWord(word);\n * bool param_2 = obj->search(word);\n */\n```
['Trie', 'C', 'C++']