题目
设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
实现 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"); // 返回 False magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True magicDictionary.search("hell"); // 返回 False magicDictionary.search("leetcoded"); // 返回 False
解题
方法一：字典树+dfs
字典树的构建就是常规的构建方法
就dfs有所区别
dfs里面有两种情况
- 当前字符在字典树中存在，继续dfs
- 暴力遍历26个字母，继续dfs。通过limit标志位去标志，只能更换一次字母。
class Trie{ public: bool isEnd=false; vector<Trie*> next=vector<Trie*>(26,nullptr); }; class MagicDictionary { public: Trie* trie=new Trie(); MagicDictionary() { } //api void buildDict(vector<string> dictionary) { for(string& word:dictionary){ insert(word); } } //api bool search(string searchWord) { return dfs(trie,searchWord,0,1); } bool dfs(Trie* node,string& word,int startIndex,int limit){//limit表示是否还能修改字母 if(startIndex==word.size()){ return limit==0&&node->isEnd; } int i=word[startIndex]-'a'; if(node->next[i]){//如果当前前缀能在字典树中找到，那么就接着dfs if(dfs(node->next[i],word,startIndex+1,limit)) return true; } if(limit==1){//如果没有修改过字母，就暴力遍历26个字母 for(int j=0;j<26;j++){ if(j!=i&&node->next[j]){ if(dfs(node->next[j],word,startIndex+1,limit-1)) return true; } } } return false; } void insert(string& word){ Trie* node=trie; for(char c:word){ if(node->next[c-'a']==nullptr){ node->next[c-'a']=new Trie(); } node=node->next[c-'a']; } node->isEnd=true; } };
