题目大意：
实现一个魔法字典
实现一个带有buildDict, 以及 search方法的魔法字典。
对于buildDict方法，你将被给定一串不重复的单词来构建一个字典。
对于search方法，你将被给定一个单词，并且判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
示例 1:
Input: buildDict(["hello", "leetcode"]), Output: Null
Input: search("hello"), Output: False
Input: search("hhllo"), Output: True
Input: search("hell"), Output: False
Input: search("leetcoded"), Output: False
注意:
- 你可以假设所有输入都是小写字母 a-z。
- 为了便于竞赛，测试所用的数据量很小。你可以在竞赛结束后，考虑更高效的算法。
- 请记住重置MagicDictionary类中声明的类变量，因为静态/类变量会在多个测试用例中保留。 请参阅这里了解更多详情。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=676
解题思路分析：
检查一个单词是否存在于一个字典之中，我们可以采用字典树Trie来解题。对于字典树，我们在之前的文章中曾提及过，如果你还没接触过这个概念，或者你对它还不太熟悉，强烈建议你去参考我之前对字典树的讲解：LEETCODE 1268. Search Suggestions System 解题思路分析。这会对你理解本题大有帮助。
本题与普通的字典树遍历有所不同，由于题目要求将单词替换一个字母后，再去查看字典树中是否存在，这需要我们在遍历时稍加改动。对于树形结构的遍历，dfs深度优先搜索是我们常用的方式，dfs递归中，我们查看当前节点的所有子节点，如果子节点为空跳过。如果子节点不为空，查看当前子节点是否是当前字母，如果相同，dfs递归至该子节点，如果dfs返回值为true，代表找到了一个合理单词，直接返回true。反之，我们可以将当前字符更改为该子节点，然后再递归至该子节点即可，同样，如果dfs返回值为true，直接返回true。注意路径中，我们只有一次更改的机会。递归的终止条件为：当遍历完字符串所有字符后，若当前节点是一个单词的结尾，并且我们使用了一次更改机会，那么说明我们找到了合理单词，返回true。反之返回false。
实现代码：
class Node{ // 字典树节点
Node[] children = new Node[26]; // 26个子节点
boolean isEndOfWord; // 当前节点是否为单词结尾
}
Node root; // 根节点
/** Initialize your data structure here. */public MagicDictionary() {
root=new Node();
}
/** Build a dictionary through a list of words */public void buildDict(String[] dict) {
for(String d : dict){ // 将每个单词加入字典树
add(d);
}
}
void add(String s){
Node r = root; // 当前根节点
char[] arr=s.toCharArray(); // 为了提高效率，将字符串转为字符数组
for(int i=0;i<arr.length;i++){ // 循环每一个字符
int c=arr[i]-'a'; // 当前字符的下标
if(r.children[c]==null){ // 如果当前子节点为空
r.children[c]=new Node(); // 新建该子节点
}
r=r.children[c]; // 将根节点设置为当前子节点
}
r.isEndOfWord=true; // 最后一个字符所在节点为true
}
/** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */public boolean search(String word) {
return dfs(root,word.toCharArray(),0,0); // dfs查看是否存在
}
boolean dfs(Node node, char[] arr, int index, int modifyCount){
if(index==arr.length){ // 递归结束条件，遍历完单词每个字符
// 如果当前节点为一个单词的结束位置，并且使用了一次修改，返回true
if(node.isEndOfWord && modifyCount==1) return true;
return false; // 返回false
}
int c = arr[index]-'a'; // 当前字符
for(int i=0;i<26;i++){ // 循环26个子节点
if(node.children[i]!=null){ // 子节点不为空
if(i==c){ // 该子节点为当前字符
// dfs递归至该子节点，修改次数不变，下标加一
if(dfs(node.children[i],arr,index+1,modifyCount)){
return true; // 递归返回结果为true，返回true。
}
}else if(modifyCount==0){ // 该子节点不是当前字符，并且还有修改次数
// dfs递归至该子节点，修改次数加一，下标加一
if(dfs(node.children[i],arr,index+1,modifyCount+1)){
return true; // 递归返回结果为true，返回true。。
}
}
}
}
return false;
} 本题解法执行时间为9ms。
Runtime: 9 ms, faster than 98.41% of Java online submissions for Implement Magic Dictionary.
Memory Usage: 38.3 MB, less than 62.06% of Java online submissions for Implement Magic Dictionary.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-676-implement-magic-dictionary-解题思路分析/