设计一个使用单词列表进行初始化的数据结构单词列表中的单词 互不相同 。 如果给出一个单词请判定能否只将这个单词中一个字母换成另一个字母使得所形成的新单词存在于你构建的字典中。实现 MagicDictionary 类MagicDictionary() 初始化对象void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构dictionary 中的字符串互不相同bool search(String searchWord) 给定一个字符串 searchWord 判定能否只将字符串中 一个 字母换成另一个字母使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以返回 true 否则返回 false 。示例输入[“MagicDictionary”, “buildDict”, “search”, “search”, “search”, “search”][[], [[“hello”, “leetcode”]], [“hello”], [“hhllo”], [“hell”], [“leetcoded”]]输出[null, null, false, true, false, false]解释MagicDictionary magicDictionary new MagicDictionary();magicDictionary.buildDict([“hello”, “leetcode”]);magicDictionary.search(“hello”); // 返回 FalsemagicDictionary.search(“hhllo”); // 将第二个 ‘h’ 替换为 ‘e’ 可以匹配 “hello” 所以返回 TruemagicDictionary.search(“hell”); // 返回 FalsemagicDictionary.search(“leetcoded”); // 返回 False提示1 dictionary.length 1001 dictionary[i].length 100dictionary[i] 仅由小写英文字母组成dictionary 中的所有字符串 互不相同1 searchWord.length 100searchWord 仅由小写英文字母组成buildDict 仅在 search 之前调用一次最多调用 100 次 search用字典树先存储dictionary中的所有单词然后search在字典树中搜索classNode{public:~Node(){for(Node*node:next){deletenode;}}vectorNode*nextvectorNode*(26,nullptr);boolisEndfalse;};classMagicDictionary{public:MagicDictionary(){rootnewNode();}~MagicDictionary(){deleteroot;}voidbuildDict(vectorstringdictionary){for(strings:dictionary){Node*curNoderoot;for(charc:s){if(curNode-next[c-a]nullptr){curNode-next[c-a]newNode();}curNodecurNode-next[c-a];}curNode-isEndtrue;}}boolsearch(string searchWord){returndoSearch(0,searchWord,root,false);}private:Node*root;booldoSearch(inti,stringsearchWord,Node*curNode,boolchanged){if(isearchWord.size()){// 如果字典树中存在此单词并且在查询过程中改变过一个字母returncurNode-isEndchanged;}charcsearchWord[i];boolfoundfalse;// 如果字典树中搜索不到相应字母if(curNode-next[c-a]nullptr){// 如果已经修改过一个字母if(changed){returnfalse;// 没有修改过字母就把当前字母改为存在的其他字母}else{for(intj0;j26;j){Node*nodecurNode-next[j];if(nodenullptr){continue;}founddoSearch(i1,searchWord,node,true);if(found){returntrue;}}}// 如果字典树中有当前字母}else{// 遍历所有存在的字母for(intj0;j26;j){Node*nodecurNode-next[j];if(nodenullptr){continue;}// 如果不是对应的字母if(aj!c){// 如果已经修改过字母就跳过if(changed){continue;// 否则试着把当前字母改为其他存在的字母}else{founddoSearch(i1,searchWord,node,true);if(found){returntrue;}}// 如果是对应字母继续向下查找}else{founddoSearch(i1,searchWord,node,changed);if(found){returntrue;}}}}returnfalse;}};/** * Your MagicDictionary object will be instantiated and called as such: * MagicDictionary* obj new MagicDictionary(); * obj-buildDict(dictionary); * bool param_2 obj-search(searchWord); */时间复杂度O(nlql2^22∣Σ∣)其中 n 是数组 dictionary 的长度l 是数组 dictionary 中字符串的平均长度q 是函数 search(searchWord) 的调用次数Σ 是字符集。初始化需要的时间为 O(nl)每一次查询最多会把与 searchWord 的每个字符相差一个字符的单词全部遍历一遍因此时间复杂度为 O(l2^22∣Σ∣)。空间复杂度O(nl)即为字典树需要使用的空间。