题目描述（中等难度）

给定一个开始单词和一个结束单词，一个单词列表，两个单词间转换原则是有且仅有一个字母不同。求出从开始单词转换到结束单词的最短路径长度是多少。

思路分析

基本上就是 126 题 的简化版了，可以先看一下 126 题 的解法思路。接下来就按照 126 题的思路讲了。把之前的图贴过来。

要求最短的路径，DFS 肯定在这里就不合适了。而在之前我们用 BFS 将每个节点的邻接节点求了出来，这个过程其实我们相当于已经把最短路径的长度求出来了。所以我们只需要把之前的 BFS 拿过来稍加修改即可。

解法一 BFS

添加一个变量 len，遍历完每一层就将 len 加 1。

public int ladderLength(String beginWord, String endWord, List<String> wordList) { if (!wordList.contains(endWord)) { return 0; } int len = 0; Queue<String> queue = new LinkedList<>(); queue.offer(beginWord); boolean isFound = false; Set<String> dict = new HashSet<>(wordList); Set<String> visited = new HashSet<>(); visited.add(beginWord); while (!queue.isEmpty()) { int size = queue.size(); Set<String> subVisited = new HashSet<>(); for (int j = 0; j < size; j++) { String temp = queue.poll(); // 一次性得到所有的下一个的节点 ArrayList<String> neighbors = getNeighbors(temp, dict); for (String neighbor : neighbors) { if (!visited.contains(neighbor)) { subVisited.add(neighbor); //到达了结束单词，提前结束 if (neighbor.equals(endWord)) { isFound = true; break; } queue.offer(neighbor); } } } //当前层添加了元素，长度加一 if (subVisited.size() > 0) { len++; } visited.addAll(subVisited); //找到以后，提前结束 while 循环，并且因为这里的层数从 0 计数，所以还需要加 1 if (isFound) { len++; break; } } return len; } private ArrayList<String> getNeighbors(String node, Set<String> dict) { ArrayList<String> res = new ArrayList<String>(); char chs[] = node.toCharArray(); for (char ch = 'a'; ch <= 'z'; ch++) { for (int i = 0; i < chs.length; i++) { if (chs[i] == ch) continue; char old_ch = chs[i]; chs[i] = ch; if (dict.contains(String.valueOf(chs))) { res.add(String.valueOf(chs)); } chs[i] = old_ch; } } return res; } 

2020.6.22 更新，感谢 @cicada 指出，leetcode 增加了 case ，上边的代码不能 AC 了，我们需要考虑从第一个单词无法转到最后一个单词的情况，所以 return 前需要判断下。

public int ladderLength(String beginWord, String endWord, List<String> wordList) { if (!wordList.contains(endWord)) { return 0; } int len = 0; Queue<String> queue = new LinkedList<>(); queue.offer(beginWord); boolean isFound = false; Set<String> dict = new HashSet<>(wordList); Set<String> visited = new HashSet<>(); visited.add(beginWord); while (!queue.isEmpty()) { int size = queue.size(); Set<String> subVisited = new HashSet<>(); for (int j = 0; j < size; j++) { String temp = queue.poll(); // 一次性得到所有的下一个的节点 ArrayList<String> neighbors = getNeighbors(temp, dict); for (String neighbor : neighbors) { if (!visited.contains(neighbor)) { subVisited.add(neighbor); //到达了结束单词，提前结束 if (neighbor.equals(endWord)) { isFound = true; break; } queue.offer(neighbor); } } } //当前层添加了元素，长度加一 if (subVisited.size() > 0) { len++; } visited.addAll(subVisited); //找到以后，提前结束 while 循环，并且因为这里的层数从 0 计数，所以还需要加 1 if (isFound) { len++; break; } } if(isFound){ return len; }else{ return 0; } } private ArrayList<String> getNeighbors(String node, Set<String> dict) { ArrayList<String> res = new ArrayList<String>(); char chs[] = node.toCharArray(); for (char ch = 'a'; ch <= 'z'; ch++) { for (int i = 0; i < chs.length; i++) { if (chs[i] == ch) continue; char old_ch = chs[i]; chs[i] = ch; if (dict.contains(String.valueOf(chs))) { res.add(String.valueOf(chs)); } chs[i] = old_ch; } } return res; } 

126 题 中介绍了得到当前节点的相邻节点的两种方案，官方题解 中又提供了一种思路，虽然不容易想到，但蛮有意思，分享一下。

就是把所有的单词归类，具体的例子会好理解一些。

一个单词会产生三个类别，比如 hot 会产生 *ot h*t ho* 然后考虑每一个单词，如果产生了相同的类，就把这些单词放在一起 假如我们的单词列表是 ["hot","dot","dog","lot","log","cog"] 考虑 hot,当前的分类结果如下 *ot -> [hot] h*t -> [hot] ho* -> [hot] 再考虑 dot,当前的分类结果如下 *ot -> [hot dot] h*t -> [hot] ho* -> [hot] d*t -> [dot] do* -> [dot] 再考虑 dog,当前的分类结果如下 *ot -> [hot dot] h*t -> [hot] ho* -> [hot] d*t -> [dot] do* -> [dot dog] *og -> [dog] d*g -> [dog] 再考虑 lot,当前的分类结果如下 *ot -> [hot dot lot] h*t -> [hot] ho* -> [hot] d*t -> [dot] do* -> [dot dog] *og -> [dog] d*g -> [dog] l*t -> [lot] lo* -> [lot] 然后把每个单词都放到对应的类中，这样最后找当前单词邻居节点的时候就方便了。 比如找 hot 的邻居节点，因为它可以产生 *ot， h*t， ho* 三个类别，所有它的相邻节点就是上边分好类的相应单词 

解法二 双向搜索

在 126 题 最后一种解法中介绍了双向搜索，大大降低了时间复杂度。当然这里也可以直接用，同样是增加 len 变量即可，只不过之前用的递归，把 len 加到全局变量会更加方便些。

int len = 2; //因为把 beginWord 和 endWord 都加入了路径，所以初始化 2 public int ladderLength(String beginWord, String endWord, List<String> wordList) { if (!wordList.contains(endWord)) { return 0; } // 利用 BFS 得到所有的邻居节点 Set<String> set1 = new HashSet<String>(); set1.add(beginWord); Set<String> set2 = new HashSet<String>(); set2.add(endWord); Set<String> wordSet = new HashSet<String>(wordList); //最后没找到返回 0 if (!bfsHelper(set1, set2, wordSet)) { return 0; } return len; } private boolean bfsHelper(Set<String> set1, Set<String> set2, Set<String> wordSet) { if (set1.isEmpty()) { return false; } // set1 的数量多，就反向扩展 if (set1.size() > set2.size()) { return bfsHelper(set2, set1, wordSet); } // 将已经访问过单词删除 wordSet.removeAll(set1); wordSet.removeAll(set2); // 保存新扩展得到的节点 Set<String> set = new HashSet<String>(); for (String str : set1) { // 遍历每一位 for (int i = 0; i < str.length(); i++) { char[] chars = str.toCharArray(); // 尝试所有字母 for (char ch = 'a'; ch <= 'z'; ch++) { if (chars[i] == ch) { continue; } chars[i] = ch; String word = new String(chars); if (set2.contains(word)) { return true; } // 如果还没有相遇，并且新的单词在 word 中，那么就加到 set 中 if (wordSet.contains(word)) { set.add(word); } } } } //如果当前进行了扩展，长度加 1 if (set.size() > 0) { len++; } // 一般情况下新扩展的元素会多一些，所以我们下次反方向扩展 set2 return bfsHelper(set2, set, wordSet); } 

当然，也可以不用递归，可以用两个队列就行了，直接把 这里 的代码贴过来供参考把，思想还是不变的。

public class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { if(!wordList.contains(endWord)) return 0; Set<String> beginSet = new HashSet<String>(), endSet = new HashSet<String>(); int len = 1; HashSet<String> visited = new HashSet<String>(); HashSet<String> dict = new HashSet<String>(wordList); beginSet.add(beginWord); endSet.add(endWord); while (!beginSet.isEmpty() && !endSet.isEmpty()) { if (beginSet.size() > endSet.size()) { Set<String> set = beginSet; beginSet = endSet; endSet = set; } Set<String> temp = new HashSet<String>(); for (String word : beginSet) { char[] chs = word.toCharArray(); for (int i = 0; i < chs.length; i++) { for (char c = 'a'; c <= 'z'; c++) { char old = chs[i]; chs[i] = c; String target = String.valueOf(chs); if (endSet.contains(target)) { return len + 1; } if (!visited.contains(target) && dict.contains(target)) { temp.add(target); visited.add(target); } chs[i] = old; } } } beginSet = temp; len++; } return 0; } } 

总

基本上和 126 题 解决思路是一样的，主要就是 BFS 的应用。解法二中，直接在递归中的基础上用全局变量，有时候确实很方便，哈哈，比如之前的 124 题。