Design a data structure that supports the following two operations:

void addWord(word)bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")addWord("dad")addWord("mad")search("pad") -> falsesearch("bad") -> truesearch(".ad") -> truesearch("b..") -> true

这题用set做的话可能会超时，应该自己定义数据结构，构造一个单词数，这样效率更高，在搜索的时候就是dfs了， 代码如下：

1 class WordDictionary { 2 public: 3     struct TreeNode{ 4     public: 5         TreeNode *child[26]; 6         bool isWord; 7  8         TreeNode() : isWord(false){ 9             for(auto & a : child)10                 a = NULL;11         }12     };13 14     WordDictionary() {15         root = new TreeNode();16     }17 18     // Adds a word into the data structure.19     void addWord(string word) {20         TreeNode * p = root;21         for(auto & a : word){22             if(!p->child[a-'a'])23                 p->child[a-'a'] = new TreeNode;24             p = p->child[a-'a'];25         }26         p->isWord = true;//标记一个单词27     }28 29 30     bool searchWord(string & word, TreeNode * p, int index)31     {32         if(word.size() == index) return p->isWord;//这条很关键33         if(word[index] == '.'){34             for(auto & a : p->child){35                 if(a && searchWord(word, a, index+1)) return true;36             }37             return false;//不要忘了38         }else{39             return (p->child[word[index] - 'a'])&&searchWord(word, p->child[word[index] - 'a'], index+1);40         }41     }42 43 46     bool search(string word) {47         return searchWord(word, root, 0);48     }49 50 51 52 53     // WordDictionary()//进入函数后会首先执行构造函数54     // : root(new TreeNode) {}55 private:56     TreeNode * root;57 };

这回写的比较乱，见谅