题目的链接在这里：https://leetcode-cn.com/problems/word-ladder-ii/
目录
题目大意
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母。
转换后得到的单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
一、示意图
二、解题思路
广度遍历 但超时了
代码如下：
class Solution {
//思路 在到达最短路径所在的层时，记录并输出所有符合条件的路劲
/**
* 1.在单词接龙的基础上，需要将找到的最短路径存储下来
* 2
*
*/
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
//结果集
List<List<String>> result=new ArrayList<>();
//创建一个String类的Set集合 利用了Set集合不能存储相同元素的原理
//因为Set集合在add的时候 会调用equals和hashcode的方法来判断元素是否重复 并把wordlist放入
Set<String> stringSet=new HashSet<>(wordList);
if(!stringSet.contains(endWord)){
//如果不包含的话 直接返回初始值
return result;
}
//已经访问过的单词集合：只找最短路径，所以之前出现的单词不用出现在下一层
Set<String> visited=new HashSet<>();
//累积每一层的结果队列
Queue<List<String>> queue=new LinkedList<>();
//先把第一层 也就是初始值放进去 要经过转换 从String->List<String>
// 应该是String转换为list 这个到底是把begin拆分成好几个 还是就一个呢 正常asList里面应该是一个String数组吧
//list 本身是个list集合 ，但他里面放的是String类型的 他创建一个ArrayList<>() 里面的参数是一个Collection
//由于String不是Collection 所以需要把String类型转化为Collection 就直接理解为通过asList来转换
List<String> list=new ArrayList<>(Arrays.asList(beginWord));
//然后放入到队列和已经访问过的单词中
queue.add(list);
visited.add(beginWord);
//是否到达符合条件的层：如果该层添加的某个单词符合目标单词，则截止该层的所有解为最短路径
boolean flag=false;
while (!queue.isEmpty()&&!flag){
//上一层的结果队列
int size=queue.size();
/**
* 该层添加的所有元素：每层必须在所有结果都添加完新的单词之后，再将这些单词统一添加到已使用
* 单词集合。 如果直接添加visited中，会导致该层绷瓷结果添加之后的相同添加行为失败
* 如：该层遇到目标单词，有两条路径都可以遇到，但是先达到的将该单词添加到 visited中，会导致第二条路无法添加
*/
Set<String> subVisited=new HashSet<>();
for(int i=0;i<size;i++){
//i是这一层队列的每一个单词 poll给出队列第一个元素并删除
//首先path 是一个String类型的list 里面很有很多String
List<String> path=queue.poll();
//获取该路径上一层的单词
String word=path.get(path.size()-1);
//把String 一个个拆分出来
char[] chars=word.toCharArray();
//用来寻找从这个单词出发的下一个符合条件的单词
for(int j=0;j<chars.length;j++){
char temp=chars[j];
//然后进行一系列暴力排除
for(char ch='a';ch<='z';ch++){
chars[j]=ch;
//再进行对比
if(ch==temp) {
//如果等于原来的 就跳过这个 循环其他的
continue;
}
//再把这个位置动过的值还原成String类型 用来进行比较
//this.value = Arrays.copyOf(value, value.length);
// String str1=String.valueOf(chars); 不知道这个可不可以
// 感觉这个也算是 String的一个构造函数 使用java.utils包中的Arrays类复制
String str=new String(chars);
//符合条件 在wordlist中并且在之前的层里面没使用 这里注意是stringSet 而不是wordlist
if(stringSet.contains(str)&&!visited.contains(str)){
//生成新路径
List<String> pathList=new ArrayList<>(path);
pathList.add(str);
//并对str进行判断是不是结果函数
if(str.equals(endWord)){
//说明可以返回结果了
flag=true;
result.add(pathList);
}
//并将该路径添加到该层队列当中
queue.add(pathList);
//将该单词添加到该层已访问的单词集合中
subVisited.add(str);
}
}
//然后还原回去
chars[j]=temp;
}
}
//并把这一层的subvisited都放回去
visited.addAll(subVisited);
}
return result;
}
}