Appearance
18 单词接龙：如何巧用深搜与广搜的变形？
今天，我们继续尝试从不同的角度（方法）来求解一个题目，通过"一题多解"的训练，拓展我们的思维。"搜索类型"的题目一直是面试考察的重点，其变形非常广，不过万变不离其宗，大部分解题方法仍然逃不开 BFS/DFS 这两个框架。
所以在本讲，我们将以一道经典的搜索题目为引，串联和使用前面学习过的各种知识点，比如：
BFS/双向 BFS
DFS
Dijkstra
具体介绍这类题目的分析和处理技巧，让你的面试得心应手。让我们马上开始。
题目
字典 wordList 中单词 beginWord 和 endWord 的转换序列是一个按下述规则形成的序列：
序列中第一个单词是 beginWord ；
序列中最后一个单词是 endWord，endWord 需要在 wordList 中；
每次转换只能改变一个字母；
转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的最短转换序列中的单词数目 。如果不存在这样的转换序列，返回 0。
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" → "hot" → "dot" → "dog" → "cog"，返回它的长度 5。
首先，这里需要重点说一下条件：
beginWord != endWord；
beginWord 可以不在 wordList 中；
endWord 必须要在 wordList 中，如果不在 wordList 中，那么需要返回 0；
所有的单词长度都一样。
预处理
拿到题目，我们要做的第一件事，应该是去挖掘题目中的隐含条件。我们看到题目中有如下条件：
每次转换只能改变一个字母；
转换过程中的中间单词必须是 wordList 里面的单词。
如果将每一次的转换，看成是图中两个点的连接，题目的最终问题就是希望我们找到图中给定两个点的最短距离。
如果把单词看成图的点，那么对应图的边又是什么呢？
注意：这里提到的图，都是指算法中的图 Graph，而不是图画 Picture。
边的由来
当我们有 word = "hit"，如果改变其中一个字母，就可以生成 "hat"。但是，我们立马发现 wordList = ["hot","dot","dog","lot","log","cog"] 并不存在单词 "hat"。
如果从图的角度来看，可以认为 <"hit", "hat"> 这条边不存在。那么接下来，我们再看一下成功的情况。
当我们有 word = "hit"，如果改变一个字母，生成 "hot"，由于 wordList[0] == "hot"，因此，这种转换 "hit" ←→ "hot" 是合法的，那么，可以认为边 <"hit", "hot"> 是存在的。
边的无向性
对于单词转换来说，当 word="hit" 可以转换成 "hot" 的时候，那么反过来 "hot" 也可以转换为 "hit"。因此，当我们得到一条边的时候，这条边就是一条无向边。
接下来我们再分析一下这类题的考点。
考点
在"13 | 搜索：如何掌握 DFS 与 BFS 的解题套路？"中，我们学习的大部分关于"图"的题目，都是明确地知道图的边，或者题目中给出了图的边。
但是，在这个题中，并没有明确地给出图的边。所有的边都需要依赖一定的条件动态生成。我们可以利用伪代码，表示边的生成，代码如下（解析在注释里）：
java
for word in Graph:
startPoint = word // 图中边起始点
for c in word:
oldChar = c
for toChar in 'a'~'z':
c = toChar
endPoint = word
if endPoint in wordList:
// 于是得到一条无向边 <startPoint, endPoint>
c = oldChar有了图的重建，再给定输入，代码如下：
java
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]经过上述操作，就可以得到题目中图的表示：
转换
如何利用字符串表示图中的点，就需要两个字符串来表示一条边。为了压缩这部分信息，我们采用整数来表示字符串。优点有以下几个方面。
字符串的处理不方便，必须使用哈希表。如果是整数表示图中的点，那么我们可以使用数组记录点的信息。
字符串的运算速度没有整数快。
我们在学习图算法的时候，大部分时候都是使用整数来表示图中的点，相对来说，对代码更加熟悉。
基于以上三个原因，我们决定将 String 表示一个点，转换为用整数表示一个点。转换的思想也比较简单：利用哈希表将不同的字符串映射到不同的整数上即可。
这里我们直接给出"建图"+"转换"的代码，如下所示（解析在注释里）：
java
class Solution {
private Map<String, Integer> wordID = null;
private List<Integer> Graph[] = null;
boolean buildGraph(String beginWord,
String endWord,
List<String> wordList) {
// 首先如果单词一样：题目中给出了条件，这两个单词必须不一样
if (beginWord.compareTo(endWord) == 0) {
return false;
}
// 需要记录每个单词的ID
wordID = new HashMap<>();
int id = 0;
for (String word: wordList) {
if (!wordID.containsKey(word)) {
wordID.put(word, id++);
}
}
// 根据题意：如果我们在wordList中找不到endWord必须要
// 返回0
if (!wordID.containsKey(endWord)) {
return false;
}
// 如果wordID中没有beginWord
// 那么把beginWord添加到wordID & wordList中
if (!wordID.containsKey(beginWord)) {
wordID.put(beginWord, id++);
wordList.add(beginWord);
}
// 构建图
Graph = new ArrayList[wordID.size()];
for (int i = 0; i < wordID.size(); i++) {
Graph[i] = new ArrayList<>();
}
for (String word: wordList) {
// 边的起始点 from
final int from = wordID.get(word);
// 看一下from能转变成什么
byte[] wordBytes = word.getBytes();
for (int i = 0; i < wordBytes.length; i++) {
byte old = wordBytes[i];
// 改变成其他byte
for (byte toByte = 'a'; toByte <= 'z'; toByte++) {
wordBytes[i] = toByte;
String toWord = new String(wordBytes);
if (wordID.containsKey(toWord)) {
// 边的终点to
int to = wordID.get(toWord);
// 把这条边加到Graph中
Graph[from].add(to);
}
}
wordBytes[i] = old;
}
}
return true;
}
public int ladderLength(String beginWord,
String endWord,
List<String> wordList) {
// 我们要写的核心代码在这里。
// 如果建图失败，说明无法找到有效解，依照题意，无解的时候
// 我们需要返回0
if (!buildGraph(beginWord, endWord, wordList)) {
return 0;
}
// 接下来我们要讨论的重点代码，还没有写!
}
}注意：在后文的代码中，我不再罗列 buildGraph 函数的详细代码，所有引用到 buildGraph 代码的地方，都是指这里的 buildGraph() 函数。
当我们建好图之后，问题就变成：
给定一个无向图；
如何求图中两个点的最短距离。
不过，根据题意，还需要注意题目要求输出的是"最短转换序列"：
一个最短转换序列是 "hit" → "hot" → "dot" → "dog" → "cog"，返回它的长度 5。
因此，最短序列等价于最短路径上的点的个数。而我们平时求的最短路径实际上是最短路径上边的数目。因此：
最短转换序列长度 = 最短路径长度 + 1
那么，到这里，我们已经将陌生的题目成功转变成非常熟悉的问题：求图中两个点的最短距离。
接下来，我们看一下具体如何破解"最短路径"问题，其实我们在"13 | 搜索：如何掌握 DFS 与 BFS 的解题套路？"的"例 2 和例 4"都学习过，你可以返回去再复习一下，以便加深对这个经典问题的理解。
BFS 算法
求两个点的最短路径的时候，我们可以直接用 BFS。为什么呢？
你应该还记得，我们在"13 | 搜索：如何掌握 DFS 与 BFS 的解题套路？"中提到过 BFS 的特点：
在搜索的时候，若想知道一些关于"最近/最快/最少"之类问题的答案，往往采用 BFS 更加适合。
因此，在这里，我们直接使用 BFS 算法。如果从 beginWord 开始搜索，那么 BFS 的搜索过程可以表达成一个"雷达波搜索"的样子------每一轮搜索都会往外扩散一圈。
你可以结合下图展示的BFS 的搜索过程示意图进一步思考，我们从 beginWord = "hit" 开始搜索，直接到找到 endWord = "cog" 时停止。
注：这里第 1 圈就是 hit 自身，蓝色圈表示 1 次搜索。
那么在写代码的时候，我们可以使用类似的技巧进行 BFS。在每一层，我们都使用一个 ArrayList 来表示。那么，可以写出基于 BFS 的代码如下（解析在注释里）：
java
class Solution {
// buildGraph的代码 ... 略...
public int ladderLength(String beginWord,
String endWord,
List<String> wordList) {
// 如果建图失败，那么返回0
if (!buildGraph(beginWord, endWord, wordList)) {
return 0;
}
// 接下来，我们就是在一个图中找到两个点的最近距离
// 这里采用BFS的方法
final int src = wordID.get(beginWord);
final int dst = wordID.get(endWord);
// 这里我们采用"两段击"的BFS的方式进行处理
List<Integer> cur = new ArrayList<>();
cur.add(src);
List<Integer> next = new ArrayList<>();
// 记录哪些点被访问过了
boolean[] vis = new boolean[wordID.size()];
vis[src] = true;
// 初始步数
int step = 0;
while (!cur.isEmpty()) {
next.clear();
step++;
// 遍历当前层的点，然后放到next中
for (Integer curNode : cur) {
// 如果走到终点
if (curNode == dst) {
return step;
}
for (Integer nextNode : Graph[curNode]) {
// 遍历边curNode -> nextNode
// 如果这个点还没有被访问过
if (!vis[nextNode]) {
// 那么放到next中
next.add(nextNode);
vis[nextNode] = true;
}
}
}
// swap the 2 list
List<Integer> tmp = cur;
cur = next;
next = tmp;
}
return 0;
}
}复杂度分析：（假设我们有 N 个单词，每个单词的长度为 M。每个单词需要更改每个位置的字母来生成新的单词）这里时间复杂度需要分为两步。
第一步：预处理建图
1. 时间复杂度
1）一共需要处理 N * M 个字母，每个字母要替换 26 次。替换之后生成的长度为 M 的新单词需要去哈希表中检验，每次去哈希表中检查一个单词需要的时间复杂度为 O(M)。
2）建图时间复杂度为 O(N * M * M * 26)，我们可以把常数 26 去掉，因此时间复杂度为 O(N * M * M)。
2. 空间复杂度
1）建图时需要建立一个有 N 个 Item，并且每个 Item 长度为 M 的哈希表。因此，哈希表空间复杂度为 O(N * M)。
2）Graph 需要占用 O(N * N) 的空间。
第二步：BFS
1. 时间复杂度
在后面 BFS 搜索的过程中，由于不会访问已访问过的点，相当于所有的点被遍历一遍，所以时间复杂度为 O(N)。
2. 空间复杂度
最差情况下，需要把所有的点都放到 Array 中，此时空间复杂度为 O(N)。
综上，整个问题的时间复杂度为 O(N * M * M)，空间复杂度为 O(max(N^2^, N * M))。
双向 BFS
如果说前面的 BFS 是"一个人"苦苦地用雷达搜索（后文中称为单向 BFS），那么会不会存在从两个方向进行搜索的情况呢？我们尝试分析一下。如果要找的目标也用雷达开启搜索，那么当两者有交互的时候，就可以认为找到了最短路径。
这种方法我们称为双向 BFS。两者的搜索过程如下图所示：
实际上，我们在写双向 BFS 的时候，两边不会同时开启搜索。而是采用一种策略：优先搜索范围更小的。
主要原因在于：
我们写算法的时候，往往不需要多线程；
优先搜索范围更小的，可以节省更多的内存，因为要存放的信息变少了。
基于这种双向 BFS 的想法，可以写出代码如下（解析在注释里）：
java
class Solution {
// 省略 buildGraph的代码 ...
public int ladderLength(String beginWord,
String endWord,
List<String> wordList){
// 如果建图失败，那么返回0
if (!buildGraph(beginWord, endWord, wordList)) {
return 0;
}
// 接下来，我们就是在一个图中找到两个点的最近距离
// 这里采用BFS的方法
final int srcNode = wordID.get(beginWord);
final int dstNode = wordID.get(endWord);
// 这里我们采用"两段击"的
// 双向BFS的方式来进行处理
// 这里正向出发
Set<Integer> src = new HashSet<>();
src.add(srcNode);
// 这里逆向出发
Set<Integer> dst = new HashSet<>();
dst.add(dstNode);
final int srcVisTag = 1;
final int dstVisTag = 2;
// 记录哪些点被访问过了
int[] vis = new int[wordID.size()];
// 通过不同的标号来标记点是被前序遍历过
// 还是被后序遍历过
vis[srcNode] = srcVisTag;
vis[dstNode] = dstVisTag;
// 初始步数
int step = 0;
while (!src.isEmpty() && !dst.isEmpty()) {
step++;
// 查看src与set是否相遇
for (Integer node : dst) {
if (src.contains(node)) {
return step;
}
}
// 哪边点更少，就更新哪一边
final int visTag = src.size() < dst.size() ?
srcVisTag : dstVisTag;
Set<Integer> tmp = src.size() < dst.size() ? src : dst;
Set<Integer> next = new HashSet<>();
for (int startNode : tmp) {
for (int nextNode : Graph[startNode]) {
if (vis[nextNode] != visTag) {
vis[nextNode] = visTag;
next.add(nextNode);
}
}
}
if (src.size() < dst.size()) {
src = next;
} else {
dst = next;
}
}
return 0;
}
}这里，我们将双向 BFS 与单向 BFS 进行一个比较，如下表所示：
那么，双向 BFS 主要的优化在于：
搜索时需要存放的信息更小了（因为搜索范围更小的优先），因此更加节省内存；
由于要处理的信息变少了，那么查找起来也会更快一些。
不过双向 BFS 还是在单向 BFS 上做常数上的优化。最差情况下，时间复杂度与空间复杂度仍然是在一个数量级的。
Dijkstra 算法
一般而言，最短路径问题，有三种：
两点之间的最短路径（BFS 算法/Dijkstra 算法/BF 算法，即Bellman-Ford 算法）；
一个点到其他所有点的最短路径（Dijkstra 算法/BF 算法）；
每两点之间的最短路径（Floyd 算法）。
现在，我们先讨论一下，在计算两点间的最短路径的时候，什么时候应该使用 BFS 算法，什么时候应该使用 Dijkstra 算法？
当图中边的权重都是 1 的时候，最好的办法是使用 BFS 算法。
当图中边的权重非负的时候，最好的办法是使用 Dijkstra 算法。
当图中的边的权重存在负值的时候，最好的办法是采用 BF 算法。
实际上，我们可以将权重为 1 的时候，看成权重不同的特例。那么，这里我们应该也可以使用 Dijkstra 算法。根据 Dijkstra 算法的思路（"03 | 优先级队列：堆与优先级队列，筛选最优元素"的"练习题 7"用到了 Dijkstra，以及"13 | 搜索：如何掌握 DFS 与 BFS 的解题套路？"的"例 5"），我们可以写出代码如下（解析在注释里）：
java
class Solution {
// .. 省略 buildGraph函数代码 ...
public int ladderLength(String beginWord,
String endWord,
List<String> wordList) {
// 如果建图失败，那么返回0
if (!buildGraph(beginWord, endWord, wordList)) {
return 0;
}
// 接下来，我们就是在一个图中找到两个点的最近距离
// 这里采用BFS的方法
final int src = wordID.get(beginWord);
final int target = wordID.get(endWord);
// 记录从src到各个点的距离
int[] dist = new int[wordID.size()];
for (int i = 0; i < dist.length; i++) {
dist[i] = wordID.size() * wordID.size() + 100;
}
dist[src] = 0;
// java小堆
Queue<Integer> Q = new PriorityQueue<>(
(v1, v2) -> dist[v1] - dist[v2]);
Q.add(src);
while (!Q.isEmpty()) {
final int startNode = Q.poll();
final int startDist = dist[startNode];
for (int nextNode : Graph[startNode]) {
final int nextDist = startDist + 1;
if (dist[nextNode] > nextDist) {
dist[nextNode] = nextDist;
Q.add(nextNode);
}
}
}
return dist[target] > wordID.size() ?
0 : dist[target] + 1;
}
}复杂度分析：时间复杂度，由于 Dijkstra 算法的时间复杂度在有 N 个点的情况下，复杂度为 O(NlgN)。但是，整个题目的时间复杂度与空间复杂度仍然由 buildGraph 函数主导。与 BFS 的时间复杂度相同。
我们再对 Dijkstra 算法做个小小的总结，在使用 Dijkstra 算法的时候，有以下特点：
并没有使用 vis 数组来进行标记；
而是当发现一个点的最小距离变得更小的时候，就需要放到优先级队列中，然后重新展开搜索。
本讲中，我们提到了 BF 算法。不过 BF 算法在有 N 个点，E 条边的情况下，时间复杂度会达到 O(N x E)。在本题中，当单词长度为 M 时，最差情况下，一个单词可以有 M x 26 条边。一个图中的边可以达到 N x M x 26。此时，时间复杂度达到 O(N x N x M x 26)，会出现超时的情况。关于这种情况，你可以自己求解一下下面这道练习题，本讲不再详细讨论。
练习题 1：有 N 个网络结点，标记为 1 到 N。给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源结点，v 是目标结点，w 是一个信号从源结点传递到目标结点的时间。
现在，我们从某个结点 K 发出一个信号。需要多久才能使所有结点都收到信号？如果不能使所有结点收到信号，则返回 -1。
DFS 算法
不知道你有没有从 Dijkstra 的算法中找到灵感？在遍历的时候，我们不再使用 vis 数组来记录一个点是否被访问，而是利用最小距离是否被更新作为条件。
那么在 DFS 的时候，是不是也可以这样操作？比如：
java
private void dfs(List<Integer> G[], int start, int[] dist)
{
for (int nextNode : G[start]) { // 边：<startNode->nextNode>
final int nextDist = dist[start] + 1;
if (nextDist < dist[nextNode]) { // 如果发现距离被更新了
dist[nextNode] = nextDist;
dfs(G, nextNode, dist); // 那么就从nextNode重新展开搜索
}
}
}那么，基于这种距离更新，就重新展开 DFS 的搜索方法，我们也可以写出新的 DFS 算法来解决这道题，代码如下（解析在注释里）：
java
class Solution {
private void dfs(List<Integer> G[], int start, int[] dist)
{
for (int nextNode : G[start]) {
final int nextDist = dist[start] + 1;
if (nextDist < dist[nextNode]) {
dist[nextNode] = nextDist;
dfs(G, nextNode, dist);
}
}
}
// .. 省略 buildGraph函数的代码 ...
public int ladderLength(String beginWord,
String endWord,
List<String> wordList) {
// 这里构图
if (!buildGraph(beginWord, endWord, wordList)) {
return 0;
}
// 分别设置好源点，终点
final int src = wordID.get(beginWord);
final int dst = wordID.get(endWord);
// 数组记录src点出发到其他点的最短距离
int[] dist = new int[wordID.size()];
// 设置一个最大距离，表示无解
int maxPathLength = wordID.size() + 1024;
// 初始化dist数组
for (int i = 0; i < dist.length; i++) {
dist[i] = maxPathLength;
}
dist[src] = 0;
// dfs搜索最优解
dfs(Graph, src, dist);
return dist[dst] >= maxPathLength ? 0 : dist[dst] + 1;
}
}复杂度分析 ：假设一共有 N 个点，那么最差情况下，每个点会被其他点最多更新 N 次。因此，最差时间复杂度为 O(N^2^)。但是就整个题目而言，时间复杂度由构建图 buildGraph 的部分主导。综上，时间复杂度为 O(N * M * M)，空间复杂度为 O(max(N^2^N * M))。
那么，接下来，我们考虑一下，Dijkstra 算法与 DFS 算法不同的地方。
虽然 Dijkstra 与 DFS 都不会再用到 vis 数组，并且都在点 nextNode 的距离被更新，然后重新展开搜索。但是依然存在不同的地方。
Dijkstra 算法是从优先级队列中拿出最优的点重新展开搜索。而且Dijkstra 算法在用一个点更新的时候，会把这个点相邻的所有点更新之后，再重新展开搜索。
而 DFS 算法却是立马从点 nextNode 重新展开搜索。
那么，有没有可能将 DFS 也改成Dijkstra这样呢？我们是不是发明了 DFS 也可以实现 Dijkstra 算法呢？基于这种思路，对 DFS 算法进行一下改写，代码如下（解析在注释里）：
java
class Solution {
// .... 省略了 buildGraph() 函数的代码 ...
private int[] dist = null;
// 优先级队列
private Queue<Integer> Q =
new PriorityQueue<>((v1, v2) -> dist[v1] - dist[v2]);
// DFS + priorityQueue
private void dfs() {
if (Q.isEmpty()) {
return;
}
final int startNode = Q.poll();
for (int nextNode : Graph[startNode]) {
final int nextDist = dist[startNode] + 1;
if (nextDist < dist[nextNode]) {
dist[nextNode] = nextDist;
Q.add(nextNode);
}
}
dfs();
// 注意：我们要用startNode把所有的点都更新完之后
// 再重新展开DFS
}
public int ladderLength(String beginWord,
String endWord,
List<String> wordList) {
if (!buildGraph(beginWord, endWord, wordList)) {
return 0;
}
final int src = wordID.get(beginWord);
final int dst = wordID.get(endWord);
// 初始化距离数组
dist = new int[wordID.size()];
int maxPathLength = wordID.size() + 1024;
for (int i = 0; i < dist.length; i++) {
dist[i] = maxPathLength;
}
dist[src] = 0;
// 优先级队列中放入src
Q.add(src);
// 进行dfs
dfs();
return dist[dst] >= maxPathLength ? 0 : dist[dst] + 1;
}
}我们发现，经过上述处理的 DFS，本质上与 Dijkstra 算法是一样的。在这里，我们将不同的算法的特点加以迁移（从原本是 Dijkstra 的特点，迁移到 DFS 算法），让不同的算法可以取得同样的效果。
总结
这一讲中，我们再次通过一个题目，挖掘了题目的信息+考点。
信息：需要通过一定的条件生成边。
考点：两点的最短路径。
当拿到这两部分信息之后，我们首先进行题目的预处理：建图 。通过建图，让题目回到了一个我们非常熟悉的知识点：两点最短路径。接来下就是匹配到了已经学过的各种知识点，轮番上阵，也就展开了不同的破题方法。最后，我把这个题目中用到的知识点整理在下面这张思维导图中，你可以参考下图梳理一遍今天学到的重点知识。
思考题
我再给你留一道思考题：在本讲介绍的题目基础上，我们找到最短的转换序列的长度 之后。如果要输出所有的最短转换序列，应该怎么办呢？
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
你可以自己尝试求解这道题目，把答案写在留言区，我们一起讨论。关于单词转换的题目就介绍到这里。接下来，下一讲介绍"19 | 最小体力消耗路径：如何突破经典题型，掌握解题模板"，让我们继续前进。
附录：题目出处和代码汇总
| 题目 | 测试链接 | BFS代码：Java/C++/Python 双向 BFS代码：Java/C++/Python Dijkstra代码：Java/C++/Python DFS + Q代码：Java/C++/Python |
|---|---|---|
| 练习题 1 | 测试链接 | 代码：Java/C++/Python |
| 思考题 | 测试链接 | 代码：Java/C++/Python |