C++ Trie
This is a vanilla application of Trie. The main difficulty lies in how to deal with the . character. I use a naive solution in this place: each time when I reac
This is a vanilla application of Trie. The main difficulty lies in how to deal with the `.` character. I use a naive solution in this place: each time when I reach a `.`, I simply traverse all the children of the current node and recursively search the remaining substring starting from each of those children.\n\n```cpp\nclass TrieNode {\npublic:\n    bool word;\n    TrieNode* children[26];\n    TrieNode() {\n        word = false;\n        memset(children, NULL, sizeof(children));\n    }\n};\n\nclass WordDictionary {\npublic:\n    /** Initialize your data structure here. */\n    WordDictionary() {\n        \n    }\n    \n    /** Adds a word into the data structure. */\n    void addWord(string word) {\n        TrieNode* node = root;\n        for (char c : word) {\n            if (!node -> children[c - \'a\']) {\n                node -> children[c - \'a\'] = new TrieNode();\n            }\n            node = node -> children[c - \'a\'];\n        }\n        node -> word = true;\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 search(word.c_str(), root);\n    }\nprivate:\n    TrieNode* root = new TrieNode();\n    \n    bool search(const char* word, TrieNode* node) {\n        for (int i = 0; word[i] && node; i++) {\n            if (word[i] != \'.\') {\n                node = node -> children[word[i] - \'a\'];\n            } else {\n                TrieNode* tmp = node;\n                for (int j = 0; j < 26; j++) {\n                    node = tmp -> children[j];\n                    if (search(word + i + 1, node)) {\n                        return true;\n                    }\n                }\n            }\n        }\n        return node && node -> word;\n    }\n};\n ```
['Backtracking', 'Trie', 'C++']