题目描述： 如果数据结构中有任何与word匹配的字符串，则bool search（word）返回true，否则返回false。 单词可能包含点“。” 点可以与任何字母匹配的地方。
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：
WordDictionary() 初始化词典对象 void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配 bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 ‘.’ ，每个 . 都可以表示任何一个字母。
示例： 输入： [“WordDictionary”,“addWord”,“addWord”,“addWord”,“search”,“search”,“search”,“search”] [[],[“bad”],[“dad”],[“mad”],[“pad”],[“bad”],[".ad"],[“b…”]] 输出： [null,null,null,null,false,true,true,true] 解释： WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord(“bad”); wordDictionary.addWord(“dad”); wordDictionary.addWord(“mad”); wordDictionary.search(“pad”); // return False wordDictionary.search(“bad”); // return True wordDictionary.search(".ad"); // return True wordDictionary.search(“b…”); // return True
提示： 1 <= word.length <= 500 addWord 中的 word 由小写英文字母组成 search 中的 word 由 ‘.’ 或小写英文字母组成 最调用多 50000 次 addWord 和 search
方法1： 主要思路： （1）使用前缀树实现；
class WordDictionary { public: //每个树的结点 struct Node{ bool is_end; unordered_map<char,Node*>children; Node(){ is_end=false; } }; Node* root;//根节点 /** Initialize your data structure here. */ WordDictionary() { root=new Node(); } /** Adds a word into the data structure. */ void addWord(string word) { //向 Node* cur=root; for(char&ch:word){ if(!(cur->children.count(ch))){ cur->children[ch]=new Node(); } cur=cur->children[ch]; } cur->is_end=true; } /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */ bool search(string word) { Node* cur=root; return helper(cur,word,0); } bool helper(Node*root,string&word,int left){ if(left==word.size()){ return root->is_end; } if(word[left]=='.'){ for(auto& it:root->children){ if(helper(it.second,word,left+1)){ return true; } } } if(root->children.count(word[left])){ return helper(root->children[word[left]],word,left+1); } return false; } }; /** * Your WordDictionary object will be instantiated and called as such: * WordDictionary* obj = new WordDictionary(); * obj->addWord(word); * bool param_2 = obj->search(word); */