字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
解题思路：BFS
这道题其实DFS和BFS都可以求解。
但是DFS会超时，因为它每一次一条路走到黑，并且还要判断哪条满足的路最短；
而BFS是一圈一圈往外扩展，题目要求的“最短”表明了BFS其实是最契合的解法。
● 方式：构造图 + BFS
题目要求这个转化序列相邻之间的单词只差一个字母，其实就等价于求每个单词的一跳邻居：
● 一跳邻居：和自己只差一个字母的单词（限定在wordList中）。可以理解为每个单词是一个点，在图中直接和自己相连的点就是自己的一跳邻居。
1、构造wordList中每个单词的一跳邻居列表（在这里为了更方便，直接记录下标）
● 定义一个HashMap<Integer, List<Integer>>，键为当前单词的下标，值为这个单词一跳邻居的下标list。（当然List<List<Integer>>也可以，直接将List的下标对应于单词的下标）
通过两层for循环，找wordList中两两之间的一跳邻居列表。并且在这个过程中使用endIndex记录下endWord的下标。
⭕ 注意：
(1) wordList中可能没有endWord（endIndex初始化为-1，如果第一步执行完毕，它仍然是-1）可以直接返回0；
(2) beginWord也要构造它的一阶邻居（尽管它可能没有出现在wordList，需要单独处理，我们将它的键设定为-1）
(3) beginWord可能也出现在wordList（为了统一处理，如果存在于wordList，我们在构造邻居的时候直接跳过wordList中beginWord）
2、BFS
● 定义一个队列，利用我们构造出来的HashMap一阶邻居信息，进行广度搜索
● 定义一个布尔类型的一维数组visited，用来记录已经处理过的单词
刚开始将-1（也就是beginWord）入队，将其（未处理过的）一跳邻居加入队列，每一跳累加path，直到找到endIndex，此时path就是最短路径长度。
class Solution {
// private int result = Integer.MAX_VALUE;
private Map<Integer, List<Integer>> map = new HashMap<>();
private boolean[] visited = new boolean[5000];
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int endIndex = -1; // endWord在wordList的下标
// 1. 先处理wordList，找一阶邻居
for(int i=0; i<wordList.size(); i++){
// 找wordList中的endWord下标
if(endWord.equals(wordList.get(i))) endIndex = i;
// endWord需要找邻居，因为它的邻居节点记录的map中需要有它
if(!beginWord.equals(wordList.get(i))){
// 给wordList每个单词找一阶邻居（存下标）
for(int j=i+1; j<wordList.size(); j++){
if(!beginWord.equals(wordList.get(j)) && isNeighbor(wordList.get(i), wordList.get(j))){
List<Integer> List1 = null;
List<Integer> List2 = null;
if(!map.containsKey(i)){
List1 = new ArrayList<Integer>();
map.put(i, List1);
}else List1 = map.get(i);
if(!map.containsKey(j)){
List2 = new ArrayList<Integer>();
map.put(j, List2);
}else List2 = map.get(j);
List1.add(j);
List2.add(i);
}
}
}
// 给beginWord找一阶邻居 键设定为-1
if(!beginWord.equals(wordList.get(i)) && isNeighbor(beginWord, wordList.get(i))){
List<Integer> beginList = null;
if(map.containsKey(-1)){
beginList = map.get(-1);
beginList.add(i);
}else{
beginList = new ArrayList<Integer>();
beginList.add(i);
map.put(-1, beginList);
}
}
}
if(endIndex == -1) return 0; // wordList没有endWord
// 2-1. 回溯(DFS，深度搜索)
// recur(-1, endIndex, 0);
// return (result > 5000) ? 0 : result;
// 2-2. 广度搜索
LinkedList<Integer> queue = new LinkedList<>();
result = 1;
queue.add(-1);
int size = queue.size();
while(!queue.isEmpty()){
int startIndex = queue.removeFirst();
size--;
if(startIndex == endIndex) return result;
if(startIndex != -1) visited[startIndex] = true;
if(map.containsKey(startIndex)){
List<Integer> neighList = map.get(startIndex);
for(int neighIndex : neighList){
if(visited[neighIndex]) continue;
queue.addLast(neighIndex);
}
}
if(size == 0){ // 这一层结束，新一层开启
size = queue.size();
result++;
}
}
return 0;
}
public boolean isNeighbor(String s1, String s2){
int i = 0;
int dif = 0;
while(i < s1.length()){
if(s1.charAt(i) != s2.charAt(i)){
dif++;
}
if(dif > 1) return false;
i++;
}
return true;
}
// public void recur(int startIndex, int targetIndex, int step){
// if(step >= result) return;
// if(startIndex == targetIndex){
// result = step + 1;
// return;
// }
// // 处理过 或者 没有邻居
// if((startIndex != -1 && visited[startIndex]) || !map.containsKey(startIndex)) return;
// if(startIndex != -1) visited[startIndex] = true;
// List<Integer> neighList = map.get(startIndex);
// for(int neighIndex : neighList){
// if(visited[neighIndex]) continue;
// recur(neighIndex, targetIndex, step+1);
// }
// if(startIndex != -1) visited[startIndex] = false;
// }
}
● 用双向BFS优化，两边一起搜索更快。
class Solution {
// private int result = Integer.MAX_VALUE;
private Map<Integer, List<Integer>> map = new HashMap<>();
// private boolean[] visited = new boolean[5000];
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int endIndex = -1; // endWord在wordList的下标
// 1. 先处理wordList，找一阶邻居
for(int i=0; i<wordList.size(); i++){
// 找wordList中的endWord下标
if(endWord.equals(wordList.get(i))) endIndex = i;
// endWord需要找邻居，因为它的邻居节点记录的map中需要有它
if(!beginWord.equals(wordList.get(i))){
// 给wordList每个单词找一阶邻居（存下标）
for(int j=i+1; j<wordList.size(); j++){
if(!beginWord.equals(wordList.get(j)) && isNeighbor(wordList.get(i), wordList.get(j))){
List<Integer> List1 = null;
List<Integer> List2 = null;
if(!map.containsKey(i)){
List1 = new ArrayList<Integer>();
map.put(i, List1);
}else List1 = map.get(i);
if(!map.containsKey(j)){
List2 = new ArrayList<Integer>();
map.put(j, List2);
}else List2 = map.get(j);
List1.add(j);
List2.add(i);
}
}
}
// 给beginWord找一阶邻居 键设定为-1
if(!beginWord.equals(wordList.get(i)) && isNeighbor(beginWord, wordList.get(i))){
List<Integer> beginList = null;
if(map.containsKey(-1)){
beginList = map.get(-1);
beginList.add(i);
}else{
beginList = new ArrayList<Integer>();
beginList.add(i);
map.put(-1, beginList);
}
}
}
if(endIndex == -1) return 0; // wordList没有endWord
// 2-1. 回溯(DFS，深度搜索)
// recur(-1, endIndex, 0);
// return (result > 5000) ? 0 : result;
// 2-2. 广度搜索
LinkedList<Integer> queue1 = new LinkedList<>();
LinkedList<Integer> queue2 = new LinkedList<>();
queue1.add(-1);
queue2.add(endIndex);
int path1 = 0;
int path2 = 0;
// 用来记录已经搜过的下标
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
// 其中一个队列为空，因为上一轮的node没有有效的邻居了，但是它刚把node加入set标记
// 而这个node可能出现在另一个队列的后几跳中
while((!queue1.isEmpty()) || (!queue2.isEmpty())){
int size1 = queue1.size();
int size2 = queue2.size();
if(size1 > 0) path1++;
// 从beginWord向endWord方向搜索
for(int i=1; i<=size1; i++){
int curIndex = queue1.removeFirst();
if(set2.contains(curIndex)) return path1 + path2 - 1;
// System.out.println("1 " + curIndex);
set1.add(curIndex);
if(map.containsKey(curIndex)){
List<Integer> neighList = map.get(curIndex);
for(int neighIndex : neighList){
if(set1.contains(neighIndex)) continue;
queue1.addLast(neighIndex);
}
}
}
if(size2 > 0) path2++;
// 从endWord向beginWord方向搜索
for(int i=1; i<=size2; i++){
int curIndex = queue2.removeFirst();
if(set1.contains(curIndex)) return path1 + path2 - 1;
// System.out.println("2 " + curIndex);
set2.add(curIndex);
if(map.containsKey(curIndex)){
List<Integer> neighList = map.get(curIndex);
for(int neighIndex : neighList){
if(set2.contains(neighIndex)) continue;
queue2.addLast(neighIndex);
}
}
}
}
return 0;
}
public boolean isNeighbor(String s1, String s2){
int i = 0;
int dif = 0;
while(i < s1.length()){
if(s1.charAt(i) != s2.charAt(i)){
dif++;
}
if(dif > 1) return false;
i++;
}
return true;
}
// public void recur(int startIndex, int targetIndex, int step){
// if(step >= result) return;
// if(startIndex == targetIndex){
// result = step + 1;
// return;
// }
// // 处理过 或者 没有邻居
// if((startIndex != -1 && visited[startIndex]) || !map.containsKey(startIndex)) return;
// if(startIndex != -1) visited[startIndex] = true;
// List<Integer> neighList = map.get(startIndex);
// for(int neighIndex : neighList){
// if(visited[neighIndex]) continue;
// recur(neighIndex, targetIndex, step+1);
// }
// if(startIndex != -1) visited[startIndex] = false;
// }
}
⭕ 注意：这里while一定是两个队列都为空了才跳出！【正常情况下是两个队列只有一个为空就跳出】！
● 【原因】为什么会这样呢？——主要是因为beginWord进行了单独处理，拥有它的一跳邻居，而wordList其他单词没有把beginWord作为一跳邻居（尽管它是）
● 在正常情况下，两个搜索的队列如果其中任意一个为空，就说明已经不连通了，不可能相遇。
● 而现在如果从endWord出发的队列为空，但是从beginWord出发的队列仍然有可能触碰到endWord搜索的元素！【原因正是上面所说】。具体来说，考虑这样一种情况：其中一个队列为空（从endWord出发的队列），因为上一轮的node没有有效的邻居了，但是它刚把node加入set标记；而这个node可能出现在另一个队列（从beginWord出发的队列）的后几跳中。
⭕ 如果不对beginWord单独处理（即wordList其他单词会将beginWord作为其中的一员），while设置为其中一个队列为空就跳出！
还可以用另一种解题思路：
● 首先保证wordList中存在endWord
● 仍然是维护一个队列，刚开始将beginWord入队
● 还需要维护一个替换次数，因此可以使用HashMap<String, Integer>，键为字符串本身，值为替换次数
● 弹出队头元素处理，用'a'-'z'去替换当前单词的每个位置（一个单词两层for）
如果替换后是endWord，那么返回替换次数
⭕ 这里可以直接返回，不用判断是否在wordList中的原因是：已经保证endWord在wordList中了！
如果替换后不是endWord，并且存在于wordList中，就将其加入队列，并维护map
代码详见：代码随想录-127. 单词接龙
