This problem is an application of the Trie data structure. In the following, it is assumed that you have solved .

Now, let's first look at the TrieNode class. I define it as follows.

1 class TrieNode {2 public:3     bool isKey;4     TrieNode* children[26];5     TrieNode(): isKey(false) {6         memset(children, NULL, sizeof(TrieNode*) * 26); 7     }8 };

The field isKey is to label whether the string comprised of characters starting from root to the current node is a key (word that has been added). In this problem, only lower-case letters a - zneed to be considered, so each TrieNode has at most 26 children. I store it in an array ofTrieNode*: children[i] corresponds to letter 'a' + i. The remaining code defines the constructor of the TrieNode class.

Adding a word can be done in the same way as in . The basic idea is to create a TrieNode corresponding to each letter in the word. When we are done, label the last node to be a key (set isKey = true). The code is as follows.

1 void addWord(string word) {2     TrieNode* run = root;3     for (char c : word) {4         if (!(run -> children[c - 'a']))5             run -> children[c - 'a'] = new TrieNode();6         run = run -> children[c - 'a']; 7     }8     run -> isKey = true;9 }

By the way, root is defined as private data of WordDictionary:

1 private:2     TrieNode* root;

And the WordDictionary class has a constructor to initialize root:

1 WordDictionary() {2     root = new TrieNode();3 }

Now we are left only with search. Let's do it. The basic idea is still the same as typical search operations in a Trie. The critical part is how to deal with the dots .. Well, my solution is very naive in this place. Each time when we reach a ., just traverse all the children of the current node and recursively search the remaining substring in word starting from that children. So I define a helper function query for search that takes in a string and a starting node. And the initial call to query is like query(word, root).

By the way, I pass a char* instead of string to query and it greatly speeds up the code. So the initial call to query is actually query(word.c_str(), root).

Now I put all the codes together below. Hope it to be useful!

1 class TrieNode { 2 public: 3     bool isKey; 4     TrieNode* children[26]; 5     TrieNode(): isKey(false) { 6         memset(children, NULL, sizeof(TrieNode*) * 26); 7     } 8 }; 9 10 class WordDictionary {11 public:12     WordDictionary() {13         root = new TrieNode();14     }15 16     // Adds a word into the data structure.17     void addWord(string word) {18         TrieNode* run = root;19         for (char c : word) {20             if (!(run -> children[c - 'a'])) 21                 run -> children[c - 'a'] = new TrieNode();22             run = run -> children[c - 'a'];23         }24         run -> isKey = true;25     }26 27     // Returns if the word is in the data structure. A word could28     // contain the dot character '.' to represent any one letter.29     bool search(string word) {30         return query(word.c_str(), root);31     }32 33 private:34     TrieNode* root;35 36     bool query(const char* word, TrieNode* node) {37         TrieNode* run = node;38         for (int i = 0; word[i]; i++) {39             if (run && word[i] != '.')40                 run = run -> children[word[i] - 'a'];41             else if (run && word[i] == '.') { 42                 TrieNode* tmp = run;43                 for (int j = 0; j < 26; j++) {44                     run = tmp -> children[j];45                     if (query(word + i + 1, run))46                         return true;47                 }48             }49             else break;50         }51         return run && run -> isKey; 52     }53 };54 55 // Your WordDictionary object will be instantiated and called as such:56 // WordDictionary wordDictionary;57 // wordDictionary.addWord("word");58 // wordDictionary.search("pattern");