- 1新手建站教程—宝塔面板的安装与使用_宝塔面板建站教程
- 2python中的async和await_python main函数 await
- 3免费分享一套SpringBoot+Vue校园论坛(微博)系统【论文+源码+SQL脚本】，帅呆了~~
- 4Ethernet 10/25G IP快速上手及PG210用户手册翻译[单次发包测试]
- 5一些解决被Github拒绝链接的方法_ubuntu github拒绝连接
- 6uiautomator2安装
- 7信息系统分析与设计 第七章 用例建模_备选事件流
- 8【二十四】springboot整合spring事务详解以及实战_springboot实现事务
- 9LLaMA、Baichuan、ChatGLM、Qwen、天工等大模型对比_chatglm qwen
- 10这些是Python 官方推荐的最好书籍（推荐）_python官方推荐的三本书
[回溯法 leetcode]126. 127 单词接龙 II I （回溯法、DFS、BFS、优化）_单词接龙回溯法
赞
踩
[回溯法 leetcode]126. 127 单词接龙 II I （回溯法、DFS、BFS、优化）
126.单词接龙 II（找出所有最短转换序列）
题目链接：https://leetcode-cn.com/problems/word-ladder-ii/
分类：回溯法、深度优先遍历、广度优先遍历、字符串、数组
题目分析
这题很明显可以用回溯法来解决，不做剪枝处理的回溯法也很好写，但本题的难点和考点主要在于对初始解法的不断优化，可以利用DFS，BFS，HashSet，HashMap等进行优化。
思路1：DFS回溯（初始解法，理解问题）
关键问题：
1、如何从字典里找到下一个可行的转换？
转换可行的条件是两个单词只能相差一个字母，如何判断两个单词只相差了一个字母？
- 方法1：构造一个判断函数，函数中设置一个计数器，每找到一个不同字符计数器就+1，如果计数器>1，返回false。枚举wordList所有M个单词需要时间复杂度O(MN)
- 方法2：将要找的节点单词的每个位置换一个字符，然后看更改后的单词在不在 wordList 中。时间复杂度O(26N)，但需要构造一个set存放wordList所有单词：
List->Set：Set<String> dict = new HashSet<>(wordList);
- 1
2、回溯法的流程
对字典做for循环，找出和当前单词只相差1个字母的元素作为它的下一个元素，进入下一层递归前要将当前单词加入当前转换序列中。
- 如果最终转换得到的单词==endWord，当前序列就加入最终序列集合res。
- 如果不能得到endWord，就退出当前递归，恢复到上一个状态。
每一个序列的构造过程中从字典选择下一个单词都是从头开始寻找，所以需要标记出已经选过的单词，避免出现死循环。
3、易忽略点：题目要求的是最短序列！
要求找的是最短转换序列，所以要设置一个最小序列长度min，序列list在加入res之前要和min比较，如果当前序列长度list.size()==min，则直接加入res即可；如果当前序列长度<min，说明res之前加入的序列都是不合格的，清空res然后加入这个更短的序列，同时更新min。
实现代码
class Solution {
List<List<String>> res = new ArrayList<>();
int min = Integer.MAX_VALUE;
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
//预处理：如果endWord不存在于wordList中则直接返回
for(int i = 0; i < wordList.size(); i++){
if(wordList.get(i).equals(endWord)) break;
if(i == wordList.size() - 1) return res;
}
List<String> list = new ArrayList<>();
list.add(beginWord);
Set<String> set = new HashSet<>();
set.add(beginWord);
backtrack(beginWord, endWord, wordList, list, set);
return res;
}
//回溯函数
public void backtrack(String curWord, String endWord, List<String> wordList, List<String> list,Set<String> set){
//寻找的是当前最短转换序列
if(list.size() > min) return;
if(curWord.equals(endWord) && list.size() <= min){
if(list.size() < min){
res.clear();
min = list.size();
}
res.add(new ArrayList<>(list));
return;
}
else{
//从字典中寻找一个可行的转换单词
for(int i = 0; i < wordList.size(); i++){
if(!set.contains(wordList.get(i)) && check(curWord, wordList.get(i))){
list.add(wordList.get(i));
set.add(wordList.get(i));
backtrack(wordList.get(i), endWord, wordList, list,set);
list.remove(list.size() - 1);
set.remove(wordList.get(i));
}
}
}
}
//判断两个单词是否只相差一个字母，且不同的字母处于相同位置。
//如果两个单词完全一样，也返回false
public boolean check(String word1, String word2){
int count = 0;
for(int i = 0; i < word1.length(); i++){
if(word1.charAt(i) != word2.charAt(i)) count++;
if(count > 1) return false;
}
return count == 1;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 存在的问题：超时。
思路2：DFS回溯 + BFS寻找最短序列长度
思路1可以做很多方面的优化，思路2是通过BFS找出从beginWord到endWord的最短序列长度，在确定了最短序列长度后，一旦出现序列list.size()>最短长度就直接return中断当前回溯过程。
关键问题：
1、如何将问题转化为图问题？
把beginWord看做图上一个节点，它的所有邻接点就是wordList里所有和它只有一个字母之差的单词，以此类推。
所以问题转化为如何找到一个单词的所有邻接点？
（1）保存每一个节点及其所有邻接点的数据结构是什么？map，key=String,value=ArrayList，key存放当前单词，value存放邻接点列表。
（2）对于每个单词，都遍历wordList，找出和它只有一个字母之差的单词加入map对于的value中，寻找目标单词的方法使用的是思路1->关键问题1->方法2。同时，为了避免出现死循环，我们这里构造的图是单向图，对于已经加入这一轮序列的节点就不能再作为其他节点的邻接点了，例如：beginWord=“hit”->“hot”，如果wordList里也存在一个"hit"，如果再用"hot"->"hit"就会构成一个死循环。所以对于每一个邻接点先判断是否曾经出现在序列list中（list.contains(节点值)），如果出现过，则在遍历邻接点时直接跳过这一节点。
（3）特殊处理：如果在寻找邻接点的过程中得到一个单词==“endWord”，就立即break，将当前的序列加入res。
2、如何进行BFS？借助队列 + 如何在BFS过程中找到最短序列长度？
找到每一个节点的所有邻接点之后，得到一个map，相当于得到一张图，接下来就是对这张图做BFS。BFS就是对图做层次遍历，借助一个队列，对于每个节点都将它的所有邻接点入队，然后通过for循环一次性对所有邻接点做检验，每一邻接点再将它的所有邻接点入队，以此类推，就是层次遍历的思路，直到队列为空或者找到endWord。
BFS的目的是为了找到最短序列长度，维护一个变量minLen，BFS每深入一层，minLen+1，直到找到endWord就退出BFS，得到最短序列长度minLen.
知识点：set，map，String，char[]
set、map
String->char[] : str.toCharArray()
char[]->String : String.valueOf(数组名)
- 1
- 2
- 3
- 4
实现时遇到的问题：
1、if(found) break的位置
这个问题在实现时卡了很久，是易错点！！！ 这一语句存在于bfs函数中，作用是如果在bfs寻找邻接点的过程中遇到endWord就标记found = true，以省去后面的BFS。
在BFS构造邻接表的过程中不能少了这一句，如果不在找到endWord时退出BFS，则会构造出：beginWord -> … -> endWord -> … -> beginWord这样的环路，导致死循环。
如果这一语句在找到endWord后就立刻执行，相当于找到endWord就立刻退出当前BFS过程，可能会丢失其他有效的转换序列。
所以这一语句必须在当前层所有节点都处理完才执行，在代码中所在位置如下：
2、在找到最短序列长度后，就可以增加一个递归出口：
if(!curWord.equals(endWord) && list.size() >= minLen) return;
//如果list长度超过最短序列长度时还没找到endWord，则直接return .
- 1
- 2
实现代码
class Solution {
List<List<String>> res = new ArrayList<>();
int minLen = 1;//最短序列长度
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
//预处理
Set<String> set = new HashSet<>(wordList);//将wordList转成set
if(!set.contains(endWord)) return res;//如果wordList里不包含endWord则直接返回。
List<String> list = new ArrayList<>();//存放当前转换序列
list.add(beginWord);
//获取邻接节点图和minLen
Map<String, ArrayList<String>> map = getMinLen(beginWord, endWord, set);
backtrack(beginWord, endWord, wordList, list, map);
return res;
}
//回溯函数
public void backtrack(String curWord, String endWord, List<String> wordList, List<String> list, Map<String, ArrayList<String>> map){
if(!curWord.equals(endWord) && list.size() >= minLen) return;//如果list长度超过现有的最短序列长度，则直接返回
if(curWord.equals(endWord) && list.size() == minLen){//如果得到一个长度<=当前最短序列长度的序列时
res.add(new ArrayList<>(list));
return;
}
else{
//获取当前节点的邻接点
ArrayList<String> neighbors = map.get(curWord);
//枚举所有邻接点,即可行的转换单词
for(int i = 0; i < neighbors.size(); i++){
String neighbor = neighbors.get(i);
//如果邻接点已经存在于当前构造的序列中，则直接跳过，避免死循环
if(list.contains(neighbor)) continue;
//所有邻接点都是可行的转换点，所以不必再做可行性判断
list.add(neighbor);
backtrack(neighbor, endWord, wordList, list, map);
list.remove(list.size() - 1);
}
}
}
//判断两个单词是否只相差一个字母，且不同的字母处于相同位置。
//方法1：
// public boolean check(String word1, String word2){
// int count = 0;
// for(int i = 0; i < word1.length(); i++){
// if(word1.charAt(i) != word2.charAt(i)) count++;
// if(count > 1) return false;
// }
// return count == 1;//如果两个单词完全一样，也返回false
// }
//方法2：返回word在dict中的所有邻接点（邻接点就是可以转换的单词）
public ArrayList<String> getNeighbor(String word, Set<String> dict){
ArrayList<String> neighbors = new ArrayList<>();
char[] chars = word.toCharArray();
for(char ch = 'a'; ch <= 'z'; ch++){
for(int i = 0; i < chars.length; i++){
char old_char = chars[i];//备份原来的字母
if(ch == chars[i]) continue;
chars[i] = ch;//将第i位替换为某个字母
String newWord = String.valueOf(chars);//构成新的单词
if(dict.contains(newWord)){//如果dict存在这个新单词，说明找到一个邻接点，加入neighbors
neighbors.add(newWord);
}
chars[i] = old_char;//还原原来的单词
}
}
return neighbors;
}
//BFS寻找最短序列长度，同时在BFS过程中构造图（map）
public Map<String, ArrayList<String>> getMinLen(String curWord, String endWord, Set<String> set){
//队列用于完成BFS
Queue<String> queue = new LinkedList<>();
queue.offer(curWord);
Map<String, ArrayList<String>> map = new HashMap<>();//存放最终要返回的图
boolean found = false;
//流程和层次遍历相同
while(!queue.isEmpty()){
int n = queue.size();
minLen++;//每执行一轮循环则最短序列长度+1
//一次性处理所有同一层节点
for(int i = 0; i < n; i++){
String top = queue.poll();
ArrayList<String> neighbors = getNeighbor(top, set);//获取当前节点的所有邻接点
map.put(top, neighbors);//加入map
//将所有邻接点再加入队列，同时注意判断是否遇到endWord
for(String neighbor : neighbors){
if(neighbor.equals(endWord)) found = true;//不立刻break，因为要把当前层构造完，以便后面基于这一层构造转换序列
queue.offer(neighbor);
}
}
if(found) break;//易错点！!!!！！必须在当前层所有节点都处理完才判断found，如果在错误位置判断或不判断则会造成回路，导致死循环。
}
return map;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 存在的问题：可以通过前20个用例，但还是超时。
思路2继续优化：map标记每个节点最早出现的层数
思路2在思路1的基础上所做的优化包括：1、BFS找出最短序列长度，2、找出每个节点的转换可行节点(即邻接点)构成邻接表，3、当前序列曾经出现过的单词在这一轮后续的寻找中不能再次使用，避免出现死循环。
第3点还可以继续优化：不仅当前序列曾经使用的单词不能再次使用，其他序列构造过程中使用过的单词也有一部分在DFS时可以不用再做处理。
关键问题：
1、哪些单词不需要在DFS中再做处理？
如图：
当前节点要取某个邻接点之前，先判断该邻接点最早出现在哪一层，如果该邻接点最早出现的层数比当前节点所在层数还要小，说明之前早就处理过这个邻接点了，因此之前的序列肯定比当前序列要短，可以直接跳过该邻接点。
例如上图的两个abc。
2、如何标记每个单词最早出现的层数？
在BFS过程中，设置一个hashMap 命名为distance ，保存每个节点最早出现的层数，每得到一个节点的所有邻接点，就判断这些邻接点是否存在于该map中，如果不存在，则说明是第一次遇到该节点，加入map并保存当前层数，如果已存在，则直接跳过。
3、如何将2应用到算法中？
最后在回溯法过程中，对于每个邻接点先判断它最早出现的层数和当前节点层数的关系，如果邻接点最早层数<=当前节点层数，则直接跳过该邻接点，否则继续按正常流程执行。
实现代码
class Solution {
List<List<String>> res = new ArrayList<>();
int minLen = 1;//最短序列长度
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
//预处理
Set<String> set = new HashSet<>(wordList);//将wordList转成set
if(!set.contains(endWord)) return res;//如果wordList里不包含endWord则直接返回。
List<String> list = new ArrayList<>();//存放当前转换序列
list.add(beginWord);
Map<String, Integer> distance = new HashMap<>();//存放每个节点及其最早出现的层数
//获取邻接节点图和minLen
Map<String, ArrayList<String>> map = bfs(beginWord, endWord, set, distance);
backtrack(beginWord, endWord, wordList, list, map, distance);
return res;
}
//回溯函数
public void backtrack(String curWord, String endWord, List<String> wordList, List<String> list, Map<String, ArrayList<String>> map, Map<String, Integer> distance){
if(!curWord.equals(endWord) && list.size() >= minLen) return;//如果list长度超过现有的最短序列长度，则直接返回
if(curWord.equals(endWord) && list.size() == minLen){//如果得到一个长度<=当前最短序列长度的序列时
res.add(new ArrayList<>(list));
return;
}
else{
//获取当前节点的邻接点
ArrayList<String> neighbors = map.get(curWord);
//枚举所有邻接点,即可行的转换单词
for(int i = 0; i < neighbors.size(); i++){
String neighbor = neighbors.get(i);
//如果邻接点所在层数<=当前节点所在层数，则直接跳过该邻接点
if(distance.get(neighbor) <= distance.get(curWord)) continue;
//如果邻接点已经存在于当前构造的序列中，则直接跳过，避免死循环
if(list.contains(neighbor)) continue;
//所有邻接点都是可行的转换点，所以不必再做可行性判断
list.add(neighbor);
backtrack(neighbor, endWord, wordList, list, map, distance);
list.remove(list.size() - 1);
}
}
}
//判断两个单词是否只相差一个字母，且不同的字母处于相同位置。
//方法2：返回word在dict中的所有邻接点（邻接点就是可以转换的单词）
public ArrayList<String> getNeighbor(String word, Set<String> dict){
ArrayList<String> neighbors = new ArrayList<>();
char[] chars = word.toCharArray();
for(char ch = 'a'; ch <= 'z'; ch++){
for(int i = 0; i < chars.length; i++){
char old_char = chars[i];//备份原来的字母
if(ch == chars[i]) continue;
chars[i] = ch;//将第i位替换为某个字母
String newWord = String.valueOf(chars);//构成新的单词
if(dict.contains(newWord)){//如果dict存在这个新单词，说明找到一个邻接点，加入neighbors
neighbors.add(newWord);
}
chars[i] = old_char;//还原原来的单词
}
}
return neighbors;
}
//BFS寻找最短序列长度，同时在BFS过程中构造图（map）
public Map<String, ArrayList<String>> bfs(String curWord, String endWord, Set<String> set, Map<String, Integer> distance){
//队列用于完成BFS
Queue<String> queue = new LinkedList<>();
queue.offer(curWord);
distance.put(curWord, minLen);
Map<String, ArrayList<String>> map = new HashMap<>();//存放最终要返回的图
boolean found = false;
//流程和层次遍历相同
while(!queue.isEmpty()){
int n = queue.size();
minLen++;//每执行一轮循环则最短序列长度+1
//一次性处理所有同一层节点
for(int i = 0; i < n; i++){
String top = queue.poll();
ArrayList<String> neighbors = getNeighbor(top, set);//获取当前节点的所有邻接点
map.put(top, neighbors);//加入map
//将所有邻接点再加入队列，同时注意判断是否遇到endWord
for(String neighbor : neighbors){
//如果当前节点未加入distance，说明是第一次遇到，加入到distance中，value=当前层数
if(!distance.containsKey(neighbor)){
distance.put(neighbor, minLen);
if(neighbor.equals(endWord)) found = true;//不立刻break，因为要把当前层构造完，以便后面基于这一层构造转换序列
queue.offer(neighbor);//未加入distance的节点才继续寻找邻接点。
}
}
}
if(found) break;//易错点！!!!！！必须在当前层所有节点都处理完才判断found，如果在错误位置判断或不判断则会造成回路，导致死循环。
}
return map;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 可以AC，但效率较低。
思路3：单向BFS（代码更简单）
基本的BFS：使用一个队列来实现BFS，队列存放的是长度相等的构造中的序列，每一轮BFS就取出队列中所有长度相等的序列继续构造，每一个序列就取出序列的最后一个节点，调用getNeighbor()寻找该节点的所有邻接点，如果邻接点没有在之前的所有序列中出现过（细节！见关键问题1）就加入到当前序列中，再将新生成的序列加入队列。
如果邻接点中出现endWord就将当前序列连同endWord加入最终结果集合res中。
关键问题：
1、如何判断邻接点是否曾经出现在序列中？（关键）
设置一个set，命名used，每个邻接点就先查看是否包含在used中：
if(used.contains(neighbor)) continue;//如果邻接点在序列中出现过则直接跳过
- 1
如果已经存在used中就直接跳过。
但需要注意，used不是每遇到一个单词就直接加入used。要理清这个问题需要先明确：队列存放的是等长的构造中的序列，如图：
图上红色框内的是假设当前BFS运行到这一阶段，队列里保存的就是一个个不同颜色的圈里的序列，这些序列长度相等，且都在构造中。接下来对每个序列都取最后一个单词，获取它的所有邻接点。
BFS一轮for循环的目的：就是把这一层的所有序列（队列中所有等长的序列）最后面加上一个邻接单词，然后重新加入到队列中，
例如：队列中原来有两个序列：hit->hot 和hit->git，endWord是goe，dict还存在一个got，
执行一轮BFS的for循环，将hot的邻接单词got加入到序列1的末尾，得到hit->hot->got，然后重新入队；同时got也是git的邻接单词，也可以加入到序列2的末尾，得到hit->git->got，所以这一层每个序列可选的邻接单词是互不影响的，不会因为这个序列使用了，那个序列就不能再使用。
所以，used负责记录的是在这一层之前的所有序列使用过的单词，例如在处理第3层节点时，used里记录的是所有序列在前两层里使用到的：hit,hot,git，这些单词不能再使用了。
因此，used每次都是在这一层的所有序列都处理完毕再更新，更新一次加入used的是这一层所有加入序列的单词，所以就需要在每一序列的处理过程中设置一个subVisited用于记录每个这一层使用的单词，但不马上更新到used里，直到这一层所有序列都处理完毕，再调用used.addAll(subVisited)加入到used中。
2、BFS比起DFS+BFS有什么优点？
（1）不需要提前计算最短序列长度minLen，因为在BFS过程中最先找到endWord的序列就是最短序列。
（2）不需要使用一个map统计每个节点和它最早出现的层数。
实现代码
class Solution {
List<List<String>> res = new ArrayList<>();
int minLen = 1;//最短序列长度
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
//预处理
Set<String> set = new HashSet<>(wordList);//将wordList转成set
if(!set.contains(endWord)) return res;//如果wordList里不包含endWord则直接返回。
bfs(beginWord, endWord, set);
return res;
}
//BFS寻找最短序列长度，同时在BFS过程中构造图（map）
public void bfs(String beginWord, String endWord, Set<String> set){
//队列用于完成BFS，存放的每个元素是一整个序列
Queue<ArrayList<String>> queue = new LinkedList<>();
ArrayList<String> path = new ArrayList<>();//存放构造中的序列
path.add(beginWord);
queue.offer(path);
//set用于记录序列里出现过的单词
Set<String> used = new HashSet<>();
used.add(beginWord);
//标记是否遇到endWord
boolean found = false;
//流程和层次遍历相同
while(!queue.isEmpty()){
int n = queue.size();//获取当前存在的序列个数
Set<String> subVisited = new HashSet<>();
//一次性处理所有构造到同一长度的序列
for(int i = 0; i < n; i++){
ArrayList<String> temp = queue.poll();
String last = temp.get(temp.size() - 1);//获取当前序列的最后一个单词
ArrayList<String> neighbors = getNeighbor(last, set);//获取当前节点的所有邻接点
//将邻接点分别加入path构造一个个新序列再入队，同时注意判断是否遇到endWord
for(String neighbor : neighbors){
if(used.contains(neighbor)) continue;//如果邻接点在序列中出现过则直接跳过
if(neighbor.equals(endWord)){
temp.add(neighbor);
res.add(new ArrayList<>(temp));
temp.remove(path.size() - 1);
found = true;//说明找到一个解，但不能马上break，继续遍历这一层的剩余邻接点，因为可能后续还有别的有效序列
}
temp.add(neighbor);
queue.offer(new ArrayList<>(temp));
temp.remove(temp.size() - 1);
subVisited.add(neighbor);
}
}
used.addAll(subVisited);
if(found) break;//易错点！！！在这一层得到最短序列后就直接返回，因为后面就是对下一层节点的处理，得到的有效序列长度必然>最短序列
}
return;
}
//判断两个单词是否只相差一个字母，且不同的字母处于相同位置。
//方法2：返回word在dict中的所有邻接点（邻接点就是可以转换的单词）
public ArrayList<String> getNeighbor(String word, Set<String> dict){
ArrayList<String> neighbors = new ArrayList<>();
char[] chars = word.toCharArray();
for(char ch = 'a'; ch <= 'z'; ch++){
for(int i = 0; i < chars.length; i++){
char old_char = chars[i];//备份原来的字母
if(ch == chars[i]) continue;
chars[i] = ch;//将第i位替换为某个字母
String newWord = String.valueOf(chars);//构成新的单词
if(dict.contains(newWord)){//如果dict存在这个新单词，说明找到一个邻接点，加入neighbors
neighbors.add(newWord);
}
chars[i] = old_char;//还原原来的单词
}
}
return neighbors;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 存在的问题：效率比优化的思路2低。
127.单词接龙 I （只需计算最短转换序列长度）
题目链接：https://leetcode-cn.com/problems/word-ladder/submissions/
分类：广度优先遍历、字符串、数组
题目分析
这题就是126的其中一步，用广度优先遍历就能计算得到最短序列长度，不需要像126题一样找到所有有效的最短转换序列，只需要找到一个最短序列，得到最短序列长度即可。
思路1：单向BFS
关键问题
1、寻找邻接点时使用set避免出现死循环，和126题的不同之处
在寻找每个节点的邻接点，构建邻接表时要避免出现死循环，所以需要使用一个全局set记录每一个使用过的单词，只要这个遇到某个单词，就将其加入全局set中。
这里不需要和126题一样再使用一个局部的subUsed，因为126引入subUsed的目的是为了每一轮构造的序列之间选择的单词互不影响，分析见126 关键问题1，最终是为了能够得到所有有效的最短转换序列，避免出现遗漏。
而本题不需要找出所有的有效序列，只需要找到第一个最短序列，得到最短的序列长度即可，所以不需要subUsed。
实现代码：
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
if(!set.contains(endWord)) return 0;
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
//已在序列中使用过的单词加入used中，不能再使用避免出现死循环
Set<String> used = new HashSet<>();
used.add(beginWord);
int minLen = 1;
while(!queue.isEmpty()){
int n = queue.size();
minLen++;
//Set<String> subUsed = new HashSet<>();
for(int i = 0; i < n; i++){
//获取队首节点
String top = queue.poll();
//获取该节点的所有邻接点
ArrayList<String> neighbors = getNeighbors(top, set);
for(String neighbor : neighbors){
if(used.contains(neighbor)) continue;
if(neighbor.equals(endWord)) return minLen;
queue.offer(neighbor);
used.add(neighbor);
}
}
//used.addAll(subUsed);
}
return 0;
}
//寻找当前节点的所有邻接节点，返回一个列表
public ArrayList<String> getNeighbors(String beginWord, Set<String> set){
//先将字符串转换为字符数组
char[] chars = beginWord.toCharArray();
//存放当前节点的所有邻接点
ArrayList<String> res = new ArrayList<>();
for(int i = 0; i < beginWord.length(); i++){
for(char ch = 'a'; ch <= 'z'; ch++){
if(ch == chars[i]) continue;
char old_ch = chars[i];
chars[i] = ch;//替换第i位字符
if(set.contains(String.valueOf(chars))) res.add(String.valueOf(chars));
chars[i] = old_ch;//还原第i位字符
}
}
return res;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
思路2：双向BFS（效率最高）
分别从beginWord和endWord为起点做BFS，两个BFS都使用对应的set来代替队列完成bfs流程：beginSet,endSet，实现的功能和队列相同，但更易于遍历。
当两个BFS流程遍历到同一个节点时，说明找到一条最短路径，返回该路径的长度即为最短路径长度。
和思路1一样设置一个全局set记录每一个使用过的单词，避免出现死循环。但因为要找的是两个BFS流程中第一个相同的节点，也就是判断其中一个set的邻接点是否存在于另一个set中，这样就必然会出现节点重复使用的情况，所以全局set要在节点相遇判断之后再做判断。
关键问题：
1、如何从两个起点出发分别做BFS？
每一轮都取邻接点更少的那个方向做BFS，邻接点的数目==两个set.size()。
为了简化代码用一段BFS代码就能涵盖两个方向的BFS，把进行BFS的对象统一设置为beginSet：
- 如果当前beginSet.size()<=endSet.size()，则不做其他处理直接进入BFS；
- 如果当前beginSet.size()>endSet.size()，则实际要做bfs的是end方向，但这里把beginSet和endSet调换，对于后续的bfs过程来说仍然是对beginset做处理。
这样bfs只需要保留一份以beginset为对象的代码即可。
实现遇到的问题
1、set无法用set.get(index)来访问元素。
改用for(String word : set) 来遍历。
2、构造完newWord之后，endset判断是否包含newWord要在used判断是否包含newWord之前执行，因为used可能包含有从endWord出发时遍历到的单词，而我们要找的就是beginSet,endSet里第一个相同的单词，如果先做used判断则找到的相同单词会被跳过。（易错点，关键点！！！）
实现代码：
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if(!wordSet.contains(endWord)) return 0;
//两个set分别用于BFS，代替bfs所需的队列
Set<String> beginSet = new HashSet<>();
Set<String> endSet = new HashSet<>();
beginSet.add(beginWord);
endSet.add(endWord);
//记录使用过的单词,避免出现死循环
Set<String> used = new HashSet<>();
int minLen = 1;
while(!beginSet.isEmpty() && !endSet.isEmpty()){
//找出可选节点更少的bfs方向,令其=beginSet
if(beginSet.size() > endSet.size()){
Set<String> temp = endSet;
endSet = beginSet;
beginSet = temp;
}
Set<String> newBeginSet = new HashSet<>();//用于更新beginSet，因为beginSet每次只记录当前层的节点，且在寻找邻接点过程中不能把邻接点立即加入beginSet，这样会导致for-word循环出现混乱
//对beginSet当前一层的所有节点寻找邻接节点
for(String word : beginSet){//遍历当前一层的每一个节点
//将当前单词转换为字符数组
char[] chars = word.toCharArray();
//遍历当前节点的所有邻接点
for(int i = 0; i < chars.length; i++){
for(char ch = 'a'; ch <= 'z'; ch++){
if(ch == chars[i]) continue;
char old_ch = chars[i];
chars[i] = ch;
String newWord = String.valueOf(chars);
//字典里如果包含新构造的单词时
if(wordSet.contains(newWord)){
//注意：endset判断是否包含newWord要在used判断是否包含newWord之前执行，因为used可能包含有从endWord出发时遍历到的单词，而我们要找的就是beginSet,endSet里第一个相同的单词，如果先做used判断则找到的相同单词会被跳过。
if(endSet.contains(newWord)) return minLen + 1;
if(!used.contains(newWord)){
used.add(newWord);
//记录这一层所找到的有效邻接点
newBeginSet.add(newWord);
}
}
chars[i] = old_ch;//还原单词
}
}
}
//更新beginSet
beginSet = newBeginSet;
minLen++;//无论哪个方向的BFS，每深入一层minLen就+1
}
return 0;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
