84ms C++ solution, Depth-first-search
class TrieNode {\n    public:\n        bool isComplete;\n        TrieNode * ch[26];\n        // Initialize your data structure here.\n        TrieNode() {\n    
    class TrieNode {\n    public:\n        bool isComplete;\n        TrieNode * ch[26];\n        // Initialize your data structure here.\n        TrieNode() {\n            isComplete = false;\n            for (int i = 0; i < 26; i++) ch[i] = NULL;\n        }\n    };\n    \n    class Trie {\n    public:\n        Trie() {\n            root = new TrieNode();\n        }\n    \n        // Inserts a word into the trie.\n        void insert(string word) {\n            // just insert one path from root node to the end\n            TrieNode * p = root;\n            for (auto c : word) {\n                if (p->ch[c-'a'] == NULL) {\n                    p->ch[c-'a'] = new TrieNode();\n                }\n                p = p->ch[c-'a'];\n            }\n            p->isComplete = true;\n        }\n    \n        // Returns if the word is in the trie.\n        bool search(string word) {\n            return dfs(root, word, 0);\n        }\n        \n        bool dfs(TrieNode* p, string& word, int startIndex) {\n            if (p == NULL) return false;\n            if (startIndex == word.length()) return p->isComplete;\n            char c = word[startIndex];\n            if (c == '.') {\n                for (int i = 0; i < 26; i++) {\n                    if (p->ch[i] != NULL) {\n                        if (dfs(p->ch[i], word, startIndex + 1)) return true;\n                    }\n                }\n                return false;\n            } else {\n                return dfs(p->ch[c - 'a'], word, startIndex + 1);\n            }\n        }\n        \n    private:\n        TrieNode* root;\n    };\n    \n    class WordDictionary {\n        Trie trie;\n    public:\n    \n        // Adds a word into the data structure.\n        void addWord(string word) {\n            trie.insert(word);\n        }\n    \n        // Returns if the word is in the data structure. A word could\n        // contain the dot character '.' to represent any one letter.\n        bool search(string word) {\n            return trie.search(word);\n        }\n        \n    \n    };
['Backtracking', 'Depth-First Search']