给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
这道题是非常的难，思想是比较复杂的，并且需要注意的点是由于写完整个代码时非常冗长的，因此出现bug是很正常的，也需要你认真的进行排查。
我也会在以后的代码里多用注解，保证代码更好的可读性。
本题的思路是转化为一张图。先将所有的单词都给保存下来，保存id 和 string 一一对应的映射关系。
然后将所有单词都用图保存下来。
最后用队列保存所有的记录。
代码如下(详细注释):
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
//答案
List<List<String>> ans = new ArrayList<>();
//word 转化为 ID的哈希表
HashMap<String,Integer> wordToId= new HashMap<>();
//id转化为word的数组
List<String> IdToWord = new ArrayList<>();
int id = 0;
for (String word : wordList){
wordToId.put(word,id++);
IdToWord.add(word);
}
//wordList如果没有找到endWord
if (!wordToId.containsKey(endWord)){
return ans;
}
//加入beginWord
if (!wordToId.containsKey(beginWord)){
wordToId.put(beginWord,id++);
IdToWord.add(beginWord);
}
//创建邻接表
ArrayList<Integer>[] edges = new ArrayList[IdToWord.size()];
for (int i = 0;i < IdToWord.size(); i++){
edges[i] = new ArrayList<>();
}
//添加边
for (int i = 0; i < IdToWord.size();i++){
for (int j = i + 1; j < IdToWord.size(); j++){
//当距离为1，添加两个点为邻边
if ( distance(IdToWord.get(i),IdToWord.get(j)) == 1){
edges[i].add(j);
edges[j].add(i);
}
}
}
//这个cost记录beginword到所有点的最短距离
int[] cost = new int[IdToWord.size()];
//先一开始初始化为最大值
for (int i = 0; i < cost.length; i++){
cost[i] = Integer.MAX_VALUE;
}
//起点为0
cost[wordToId.get(beginWord)] = 0;
//找到目标点
int destId = wordToId.get(endWord);
//这个队列中保存的路径
Queue<ArrayList<Integer>> queue = new LinkedList<>();
//先将起点加入
ArrayList<Integer> begin= new ArrayList<>();
begin.add(wordToId.get(beginWord));
queue.add(begin);
//开始BFS
while (!queue.isEmpty()){
//取出一条路径
ArrayList<Integer> current = queue.poll();
//取出最后一个路径下的最后节点
int last = current.get(current.size()-1);
//判断路径的最后节点是否是endWord
if (IdToWord.get(last).equals(endWord)){
//保存下来，把ID值转化为String
ArrayList<String> tmp = new ArrayList<>();
for (int i = 0; i < current.size();i++){
tmp.add(IdToWord.get(current.get(i)));
}
ans.add(tmp);
}
else{
//记录下最后节点有多少相邻边
int size = edges[last].size();
//开始遍历
for (int i = 0; i < size; i++){
//取出相邻节点
int to = edges[last].get(i);
//判断，这里不需要判断是否访问过，因为如果访问过，那下面这个不等式一定不会成立。且需要用等号，因为不能排除相等长度的路径
if (cost[last] + 1 <= cost[to]){
//更新距离
cost[to] = cost[last] + 1;
//保存新的路径，先将之前的路径保存下来
ArrayList<Integer> tmp = new ArrayList<>(current);
//添加新的节点to，入队列
tmp.add(to);
queue.add(tmp);
}
}
}
}
return ans;
}
int distance(String a,String b){
int cnt = 0;
for (int i = 0; i < a.length();i++){
if (a.charAt(i) != b.charAt(i)){
cnt++;
}
}
return cnt;
}
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
