单词接龙II
给定两个单词（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" 不在字典中，所以不存在符合要求的转换序列。
先BFS遍历图,找到所有到达结尾单词的最短路径，同时记录图。最后再DFS遍历图。
BFS遍历图：queue用来BFS遍历图。队列按结点的深度依次存放待处理的结点。首先存放第一层结点，弹出，根据第一层结点找到所有第二层结点放入队列；弹出第二层某个结点，根据此结点找到所有第三层结点放入队列，以此类推。
记录图：记录图中每个结点的父节点们。记录图中结点的层数（深度）。
DFS遍历记录的图得出结果。
class Solution{
public boolean isDiffOneWord(String a,String b){
int diffnum=0;
for(int i=0;i<a.length();i++){
if(a.charAt(i)!=b.charAt(i)){
diffnum++;
}
if(diffnum==2){
return false;
}
}
if(diffnum==1){
return true;
}
return false;
}
public List<List<String>> findLadders(String beginWord,String endWord,List<String> wordList){
List<List<String>> res=new ArrayList<List<String>>();
int endIndex=wordList.indexOf(endWord);
if(endIndex==-1){
return res;
}
int beginIndex=wordList.indexOf(beginWord);
//若beginWord不在wordList中，则添加至wordList末尾
if(beginIndex==-1){
wordList.add(beginWord);
beginIndex=wordList.size()-1;
}
//queue用来BFS遍历图。队列按节点的深度依次存放待处理的节点。首先存放第一层结点，弹出
//根据第一层结点找到所有第二层结点放入队列；以此类推
Queue<Integer> queue=new LinkedList<Integer>();
queue.offer(beginIndex);
//fatherNodes、height用来记录图
//记录图中每个节点的父亲节点们
Map<Integer,List<Integer>> fatherNodes=new HashMap<Integer,List<Integer>>();
for(int i=0;i<wordList.size();i++){
fatherNodes.put(i,new ArrayList<Integer>());
}
//记录图中节点的层数（深度）
int[] height=new int[wordList.size()];
height[beginIndex]=1;
while(!queue.isEmpty()){
int nowIndex=queue.poll();
//若最短深度的路径已经记录完毕，退出循环
//height[nowIndex]>=height[endIndex]针对多个父亲点的情况
if(height[endIndex]!=0 && height[nowIndex]>=height[endIndex]){
break;
}
for(int i=0;i<wordList.size();i++){
//height[i]==0未访问过的节点，height[i]=height[nowIndex]+1多个父亲节点的情况，且一个父亲节点已经访问过该结点
if((height[i]==0 || height[i]==height[nowIndex]+1) && isDiffOneWord(wordList.get(nowIndex),wordList.get(i))){
if(height[i]==0){
queue.offer(i);
height[i]=height[nowIndex]+1;
fatherNodes.get(i).add(nowIndex);
}else{
//height[i]=height[nowIndex]+1多个父亲节点的情况，且一个父亲节点已经访问过该结点
fatherNodes.get(i).add(nowIndex);
}
}
}
}
if(height[endIndex]==0){
return res;
}else{
List<String> list=new ArrayList<String>();
list.add(wordList.get(endIndex));
dfs(endIndex,list,res,wordList,fatherNodes,beginIndex);
}
return res;
}
public void dfs(int lastIndex,List<String> list,List<List<String>> res,List<String> wordList,Map<Integer,List<Integer>> fatherNodes,int beginIndex){
if(lastIndex==beginIndex){
List<String> newList=new ArrayList<String>(list);
Collections.reverse(newList);
res.add(newList);
return;
}
for(int i=0;i<fatherNodes.get(lastIndex).size();i++){
int fatherIndex=fatherNodes.get(lastIndex).get(i);
list.add(wordList.get(fatherIndex));
dfs(fatherIndex,list,res,wordList,fatherNodes,beginIndex);
list.remove(list.size()-1);
}
}
}
