设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
实现 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
提示：
- 1 <= dictionary.length <= 100
- 1 <= dictionary[i].length <= 100
- dictionary[i] 仅由小写英文字母组成
- dictionary 中的所有字符串 互不相同
- 1 <= searchWord.length <= 100
- searchWord 仅由小写英文字母组成
- buildDict 仅在 search 之前调用一次
- 最多调用 100 次 search
- 我们可以定义一个HashSet用来存储dictionary的单词，接着对于每次拿到的单词searchWord的每个位置都进行’a‘ 到 ’z‘的替换，并判断替换后的字符串是否存在于HashSet中即可。
class MagicDictionary {
private Set set;
public MagicDictionary() {
set = new HashSet<>();
}
public void buildDict(String[] dictionary) {
for(String s : dictionary)
set.add(s);
}
public boolean search(String searchWord) {
for(int i=0;i
char old = searchWord.charAt(i);
for(int j=0;j<26;j++){
if(j == old - 'a')
continue;
StringBuilder s0 = new StringBuilder(searchWord);
String replaceS = "" + (char)(j + 'a');
s0.replace(i, i+1 ,replaceS);
if(set.contains(s0.toString())){
return true;
}
}
}
return false;
}
}
Solution2(字典树):
- 关于字典树，我们可以通过一个视频Trie前缀树和一个博客Java实现Trie前缀树。
借助字典树，我们可以先把dictionary字符串数组中的字符串放进字典树，接着我们对于每次要查找的searchWord，将其代入字典树进行逐个字符的查找。
-
查找时，由于是树状结构，我们可以使用递归+ 回溯，即建立一个递归函数dfs(Node node,boolean sign,String searchWord,int index) ，其中node表示此时位于字典树的节点位置，sign表示是否可以修改字母，index为此时遍历到searchWord的位置。
-
对于此时在字典树的某个节点位置，我们每次都使其向其能扩散的所有方向（即所有nodes['a'-'a']到nodes['z'-'a']不为null的节点）进行扩散，借着每次扩散后与searchWord的index位置判断，判断是否需要修改字符，需要则改变sign为false，表示已经修改一次不能再被修改，不需要则不改变sign，接着继续扩散即可。若扩散的时候发现需要修改字母但是sign已为false，则代表此路不通，进行回溯到上一次节点即可。
-
且注意由题意可知，必须要进行一次修改，所以当成功与searchWord比对完全后，还要验证sign是否为false，若为true则代表不成功。
并且此题可以进行贪心剪枝，即若searchWord为"hello"时，若是查找发现字典树内有’h’，则直接优先走’h‘，接着若有’e’，则优先走’e’，也就是能不修改就不修改，直到走到尽头判断是否可行，不可行则进行回溯；且由于此路径已经被走完，所以下面在重新向各个方向走的时候，可以剔除掉贪心剪枝未查询到的情况。
对于返回类型为布尔类型的递归函数，像下面代码中实现即可，为什么呢？
-
首先你是要进行递归，那么必定是要执行递归函数，且递归函数又是返回的布尔类型，那么就很显然是作为条件来出现的，因此刚好可以把它放到if的条件中，这样既执行了同时又能得到返回值，同时又能根据返回值进行自己的判断。
-
在实现递归时，一定要做到先大处着眼，即先大体笼罩全局，即对于上述这种我们可以先将递归函数假设已经实现，那么递归函数的使用意义就变的很清楚了。
比如上述题目，其dfs就是在只能查找从此时的节点开始，向下是否能查找到searchWord字符串从index位置到末尾位置任意剔除一个位置的字符的其他所有字符。所以在写递归函数时，我们先让自己的函数假设已经实现，接着我们只要模拟第一次进入函数即可，即先判断能否直接从贪心的方向解决，使用递归函数的返回值来判断是否解决，解决了即return true，表示成功；没解决则使其向各个方向进行移动，然后每个都判断是否走成功，成功则return true，不成功则return false，并且如果此时searchWord的index位置的字符与查找到的字典树的此时节点字符不相同，且此时sign又为false，则不成功，即return false。
| 因此实现递归函数时一定要先弄清楚自己的递归函数是干什么的，然后给其假设已经成立，接着从大局出发，模拟走一次递归的流程即可。 |
|---|
class Node{
Node[] nodes;
boolean flag;
public Node(){
nodes = new Node[26];
// 看样子是直接开了26个坑，但是其实由于每一个坑都没有new，所以都没数据，所以其实只是假开，只是把26个指向开了，
// 后面只有真正存在某个方向的元素才会真开内存。
flag = false;
}
public boolean contains(char key){
if(nodes[key - 'a'] != null)
return true;
return false;
}
public Node get(char key){
return nodes[key - 'a'];
}
public void put(char key){
nodes[key - 'a'] = new Node();
}
public void setFlag(){
flag = true;
}
public boolean checkFlag(){
return flag;
}
}
class Trie{
//分成两个类就是为了能多个头指针，这样能一直保持头指针不动，使得此类的实例化对象可以进行多次运算而不是只能用一次
Node root;
public Trie(){
root = new Node();
}
public void insert(String word){
Node temp = root;
for(int i=0;i
char c = word.charAt(i);
if(temp.contains(c)){
temp = temp.get(c);
}
else{
temp.put(c);
temp = temp.get(c);
}
}
temp.flag = true;
}
}
class MagicDictionary {
private Trie trie;
public MagicDictionary() {
trie = new Trie();
}
public void buildDict(String[] dictionary) {
for(String s : dictionary){
trie.insert(s);
}
}
public boolean search(String searchWord) {
// 头指针先判断是否为null， 这样dfs就可以不判断此时节点的情况了，只要判断此节点所链接的节点即可
if(trie.root != null){
return dfs(trie.root,true,searchWord,0);
}
else{
return false;
}
}
public boolean dfs(Node node,boolean sign,String searchWord,int index){
if(node.nodes == null)
return false;
if(index == searchWord.length()){
if(node.checkFlag() && !sign) // 题目要求必须修改一次
return true;
return false;
}
char c = searchWord.charAt(index);
// 符合条件则先根据贪心剪枝
if(node.contains(c)){
if(dfs(node.get(c),sign,searchWord,index+1)){ // 不能放index++和++index，因为要保证回溯过来的index不变！
return true;
}
}
if(sign){
sign = false;
for(int i=0;i<26;i++){
char temp = (char)(i + 'a');
if(temp == c)
continue; // 把原先贪心剪枝未查询到的情况去除，原先不符合剪枝条件的也不会受影响，因为本来就不含有temp指向
if(node.get(temp) != null){
if(dfs(node.get(temp),sign,searchWord,index+1)){
return true;
}
}
}
return false;
}
// 这里要加return,因为虽然是if-else结尾看样子直接分别在if和else里写return即可，但是由于if里不是一定return
// if里也有if，所以导致if不一定被完全return,所以外部要加上
return false;
}
}
