Leetcode | 第7节：DFS，BFS
大家好！
这一节我们介绍一下DFS和BFS，也就是深度优先搜索和广度优先搜索。搜索算法也是很多题目我们所会考虑的第一个算法，因为想法直接而易想。本来是要介绍树有关的内容的，但是研究了一下材料发现，其实树相关的题目还是挺多需要用到我们这一节说到的搜索算法的，所以我们就临时换了一下介绍顺序。
那么我们开始吧。
算法4：搜索算法（DFS/BFS）
搜索算法是一套简单直接思想，所以我们通过一道道题来看搜索算法的思想，会比单说算法是什么，更让人有印象。
DFS
Problem 1: Leetcode 40 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。
比方说candidates = [10,1,2,7,6,1,5], target = 8，那么输出就是
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
也就是说，不仅要使用里面的数字，而且要把所有的可能组合都放在一个list里面。
这一个题本质上是一个组合问题。也就是说，对于数组里的每一个元素，都有挑选和不挑选的两种方案。那么我们可以从前到后遍历，每遍历到一个元素就决定是否“选择它”。具体来说，定义dfs(pos, rest)为表示递归的函数，其中
表示遍历到的位置，
表示剩下的元素的和。那么选择这个位置的数，问题就变成了dfs(pos+1, rest - candidates[pos])。不选择，问题就变成了dfs(pos+1, rest)，并且要保证rest - candidates[pos] >= 0。最终只需要rest == 0，就说明找到了一个符合条件的元素，就可以记录下来并且返回了。
这个算法是非常标准的回溯算法（也可以算作DFS的一种。当然，它也是很多动态规划算法的思考前身），但是这个题还有一个细节。考虑candidates = [2, 2]，那么这个时候，如果target = 2，这个算法会记录两遍相同的结果[2]，不符合题目条件。当然了，其实也可以通过把list放到set里面，再放回list里面，达到去重的目的。但有没有更优雅的方法呢？
注意到这个重复，是考虑到candidates里面可能有重复元素的情况。所以如果我们可以事先决定选择这些重复元素的个数，就不会重复了。
具体来说，我们把数组中的元素都按照哈希的方法，放入freq中，然后定义freq[pos][0]表示当前第pos个数的值，而freq[pos][1]则是它出现的次数。因此，我们不仅可以选择“选不选这个数”，还可以选择“选择这个数几次”。所以如果我们选择
次，那么问题就变成了dfs(pos + 1, rest - i * freq[pos][0])。当然了，这就要保证i <= freq[pos][1]，以及rest - i * freq[pos][0] >= 0。
好的，我们来看看代码怎么写。
class Solution {
private:
vector<pair<int, int>> freq;
vector<vector<int>> ans;
vector<int> sequence;
public:
void dfs(int pos, int rest) {
if (rest == 0) {
ans.push_back(sequence);
return;
}
if (pos == freq.size() || rest < freq[pos].first) {
return; // 两种情况结束递归：已经遍历结束，和rest已经小于下一个数的值了。注意这里给数组排了一个序，所以如果下一个数的值大于rest，之后的元素肯定也大于rest，就可以直接返回了，相当于做了一点剪枝。
}
dfs(pos + 1, rest);
int most = min(rest / freq[pos].first, freq[pos].second); // 计算i最大可以为多少
for (int i = 1; i <= most; ++i) {
sequence.push_back(freq[pos].first);
dfs(pos + 1, rest - i * freq[pos].first);
}
for (int i = 1; i <= most; ++i) {
sequence.pop_back(); // 注意每一次dfs任务完成之后要把“状态还原”，也就是放进sequence的元素要再pop出来
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
for (int num: candidates) {
if (freq.empty() || num != freq.back().first) {
freq.emplace_back(num, 1);
} else {
++freq.back().second;
} // 将candidates重新排序，用哈希的方法把元素放到了freq里面
}
dfs(0, target);
return ans;
}
};
这里涉及到了一个剪枝方法，已经注释在了代码内，读者可以自己去看看。
Problem 2: Leetcode 90 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
比方说如果nums = [1,2,2]，那么输出就是[[],[1],[1,2],[1,2,2],[2],[2,2]]。
对于这个问题，其实方法和上面很类似，我们也是考虑“选或不选”，然后遍历到最后一个元素就可以返回当前选择的子集。不过重复的可能性也是一样，即如果candidates = [2, 2]，同样的子集[2]，会被我们计算两次，所以需要思考一个去重的方案。
假如我们遇到了一个数
，那么如果之前有一个相同的元素
，并且没有选择它，那么这个
之后的情况其实就不用考虑了。为什么？思考一下，如果出现这个情况，说明我们已经考虑到了
的所有情况（选择或者不选择
）。那么如果我们无论选择或者不选择这个
，所生成的子集，一定会被包含在之前“选择
而生成的子集"内，就会产生重复，因此可以直接返回。去掉这个情况之后，就可以解决这个问题。
好的，我们直接来看代码。
class Solution {
public:
vector<int> t;
vector<vector<int>> ans;
void dfs(bool choosePre, int cur, vector<int> &nums) {
if (cur == nums.size()) {
ans.push_back(t);
return;
}
dfs(false, cur + 1, nums);
if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
return; // 没有选择上一个元素 & 不是第一个元素 & 上一个元素和当前的元素相同，那么这个时候不用再考虑了，直接返回
}
t.push_back(nums[cur]);
dfs(true, cur + 1, nums); // 把元素放入t中，对应的就是选择上一个元素（true）的情况
t.pop_back(); // 回溯结束了要还原状态
}
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
sort(nums.begin(), nums.end()); // 剪枝，速度会更快
dfs(false, 0, nums);
return ans;
}
};
Problem 3: Leetcode 47 给定一个可包含重复数字的序列
nums，按任意顺序返回所有不重复的全排列。
比方说nums = [1,1,2]，那么结果就是
[[1,1,2],
[1,2,1],
[2,1,1]]
这一个问题是非常典型的全排列问题的一个改版。相比较一般情况的全排列，这里会出现重复的情况，所以要去重。
先考虑不重复的情况。我们从前往后对数组进行遍历。然后设backtrack(idx, perm)表示当前排列为perm，下一个待填入的位置为idx。可以看出，这样的话，只要idx == n，说明填完了，就可以把perm放入答案数组中。如果没有的话，就需要考虑填入一个数。这个数肯定不能是之前已经填过的。所以可以用一个数组（vis）来标记是否填过。然后进入下一步backtrack(idx+1, perm)。当然还是那句话，你下一步运行完之后，还需要状态还原。
现在考虑一下有重复的情况。事实上，处理重复的情况和之前是一模一样的。具体来说就是这么一串代码。
if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
continue;
}
分析逻辑和判断代码都和Problem 2一模一样。如果我们在位置idx选择了一个
，但是其实我们在这之前遇到过一个相同的元素
，并且没有选择过这个
，那么
之后就不用再继续了，因为所有可能的情况，都包含在了之前选择
的时候，再对
做出决策，就会产生重复。
好的，我们来看一下代码吧。
class Solution {
vector<int> vis;
public:
void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {
if (idx == nums.size()) {
ans.emplace_back(perm);
return;
}
for (int i = 0; i < (int)nums.size(); ++i) {
if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
continue;
} // 去重逻辑
perm.emplace_back(nums[i]);
vis[i] = 1;
backtrack(nums, ans, idx + 1, perm);
vis[i] = 0;
perm.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> perm;
vis.resize(nums.size()); // vis就是标记数组，标记是否有访问过
sort(nums.begin(), nums.end()); // 剪枝
backtrack(nums, ans, 0, perm);
return ans;
}
};
这个题还是有些思维量的，需要仔细理解一下如何做的去重。
Problem 4: Leetcode 130 给你一个
m x n的矩阵board，由若干字符'X'和'O'，找到所有被'X'围绕的区域，并将这些区域里所有的'O'用'X'填充。
比方说如果输入是board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]。那么输出就是[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]。对应的图如下：
最下面的那个'O'没有被处理掉，是因为它已经在边缘了，所以最下面没有'X'包围它，就不符合这个要求了。
这一个问题是很典型的用搜索算法求解的区域和图形相关的问题。简单来说，就是通过递归来模拟人“向左向右向下向上走”的过程。并且递归结束之后要进行状态还原。
但是这个题还有一个细节，就是，我们要找到什么样的'O'是“被包围的”。这里的一个关键在于，如果它不是被包围的，那么一定会和边界的'O'相连。基于这个性质，我们可以从边界出发，然后标记与边界上的'O'相连的区域。那么只要某一个地方被标记了，就说明确实这个地方与边界相连了，那么这一个地方就标记为'O'。否则的话，就标记为'X'就可以了。
好的，我们来看一下代码吧。对于DFS相关的题目来说，代码细节还是非常需要打量的。
class Solution {
public:
int n, m;
void dfs(vector<vector<char>>& board, int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') { // 只要越界/不再是'O'所属的范围，就不用再走了，应该返回了。
return;
}
board[x][y] = 'A'; // 如果符合要求，就标记，这里标记为'A'。
dfs(board, x + 1, y);
dfs(board, x - 1, y);
dfs(board, x, y + 1);
dfs(board, x, y - 1); // 模拟向各个方向走的过程
}
void solve(vector<vector<char>>& board) {
n = board.size();
if (n == 0) {
return;
}
m = board[0].size();
for (int i = 0; i < n; i++) {
dfs(board, i, 0);
dfs(board, i, m - 1);
}
for (int i = 1; i < m - 1; i++) {
dfs(board, 0, i);
dfs(board, n - 1, i);
} // 上面两个for循环都是从边界出发的
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'A') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X'; // 根据不同情况，重新标记'O'和'X'
}
}
}
}
};
一个类似的题目是Leetcode 200，但会相对更简单一些。如果对代码细节感觉容易出错，可以再拿这一个题练一练手。
Problem 5: Leetcode 547 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。 返回矩阵中 省份 的数量。
比方说输入是isConnected = [[1,1,0],[1,1,0],[0,0,1]]，那么输出就是2。对应的图如下：
可以看出，这里有2个连通分量。
这一个题的思路其实也是很传统的，用搜索算法找区域的题目，和上面几乎没有差别。但是因为这一道题涉及到了图，有一些图相关的基本操作，所以可以拿来给大家复习一下图的相关代码。
简单来说，算法就是遍历图中的节点，然后通过dfs/bfs的方式去找与这个节点相连的区域。一个区域统计一次，一直到所有点遍历完即可。这个过程如果结合代码来看，就会更加清楚明白。
class Solution {
public:
void dfs(vector<vector<int>>& isConnected, vector<int>& visited, int provinces, int i) {
for (int j = 0; j < provinces; j++) {
if (isConnected[i][j] == 1 && !visited[j]) {
visited[j] = 1;
dfs(isConnected, visited, provinces, j); // 如果i, j是相连的，并且j没有被访问过，那么访问j，下一步走到j。
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
int provinces = isConnected.size();
vector<int> visited(provinces);
int circles = 0;
for (int i = 0; i < provinces; i++) {
if (!visited[i]) {
dfs(isConnected, visited, provinces, i);
circles++; // 一个连通分量走完之后，visited状态会更新。
}
}
return circles;
}
};
这里可以看到，我们是使用了邻接矩阵存储的图。
Problem 6: Leetcode 51 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
比方说如果输入n = 4，那么这个时候对应的输出为[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]。对应的图示如下：
这一个问题是非常经典的八皇后问题（当然这里推广到了一般的
的情况）。对于这一个问题，首先大体上来看，因为每一行和每一列，都只能放置一个皇后。所以根据排列组合的思想，我们先固定行，然后再选择列的话，第一行有
种选择，第二行有
种选择，一直往后，就能够得到
个选择方案。因此最终大体上的时间复杂度是
。但是这里还需要要求皇后们不能在同一条斜线上（与对角线平行）。所以需要想办法，通过最快的速度检测皇后们是否会冲突。这个应该怎么办呢？
注意到在一个二维数组中，同一条斜线要不它的坐标和相同，要不它的坐标差相同（分别对应正反对角线，读者可以自己画图验证）。所以可以记录每一个皇后所在位置的坐标和和坐标差，然后在放置新皇后的时候，同时计算这两个值，如果没有皇后和它们的坐标和和坐标差相同，那就说明不重复，就可以继续走下一步了。
好的，我们来看看代码吧。
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
auto solutions = vector<vector<string>>();
auto queens = vector<int>(n, -1); // 固定行，每一行选择的列是哪一列，这里的列初始化为-1，表示没有被选择。
auto columns = unordered_set<int>();
auto diagonals1 = unordered_set<int>();
auto diagonals2 = unordered_set<int>(); // diagonals1, 2就是两个用来判断斜线的set，设置成set是因为这样的话判断复杂度是O(1)
backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
return solutions;
}
void backtrack(vector<vector<string>> &solutions, vector<int> &queens, int n, int row, unordered_set<int> &columns, unordered_set<int> &diagonals1, unordered_set<int> &diagonals2) {
if (row == n) {
vector<string> board = generateBoard(queens, n);
solutions.push_back(board);
} else {
for (int i = 0; i < n; i++) {
if (columns.find(i) != columns.end()) {
continue;
}
int diagonal1 = row - i; // 差相同
if (diagonals1.find(diagonal1) != diagonals1.end()) {
continue;
}
int diagonal2 = row + i; // 和相同
if (diagonals2.find(diagonal2) != diagonals2.end()) {
continue;
}
queens[row] = i;
columns.insert(i);
diagonals1.insert(diagonal1);
diagonals2.insert(diagonal2);
backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
queens[row] = -1;
columns.erase(i);
diagonals1.erase(diagonal1);
diagonals2.erase(diagonal2); // 状态还原
}
}
}
vector<string> generateBoard(vector<int> &queens, int n) {
auto board = vector<string>();
for (int i = 0; i < n; i++) {
string row = string(n, '.');
row[queens[i]] = 'Q';
board.push_back(row);
}
return board; // 生成最后的输出结果
}
};Problem 7: Leetcode 131 给你一个字符串
s，请你将s分割成一些子串，使每个子串都是 回文串 。返回s所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。
比方说这里，如果有s = "aab"，那么输出就是[["a","a","b"],["aa","b"]]。
如果前面几个题思路都很明晰，这一个题的思路也不难想，就是枚举需要切割的位置，然后判断切割位置是否合理（即是否之前那一段是一个回文串）。但是事实上这样也有一个问题，就是每一次判断回文串都是一个耗时的工作，会产生重复计算（比方说"aa"就会有两种切割方案，每一次方案都遍历，就会重复遍历第一个'a'）。因此为了避免这种情况，一个好的方案就是把所有区间是否为回文串给预先计算出来，而这一步计算可以通过动态规划来进行实现。具体的状态转移方程为
为什么是这个，相信我不用说你也能懂。
好的，我们直接给出代码。
class Solution {
private:
vector<vector<int>> f;
vector<vector<string>> ret;
vector<string> ans;
int n;
public:
void dfs(const string& s, int i) {
if (i == n) {
ret.push_back(ans);
return;
}
for (int j = i; j < n; ++j) {
if (f[i][j]) { // f[i][j]就是动态规划的数组，用于判断s[i...j]是否是一个回文串
ans.push_back(s.substr(i, j - i + 1));
dfs(s, j + 1);
ans.pop_back(); // 状态还原
}
}
}
vector<vector<string>> partition(string s) {
n = s.size();
f.assign(n, vector<int>(n, true));
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1]; // 状态转移方程
}
}
dfs(s, 0);
return ret;
}
};
这一个题目还可以通过记忆化搜索来进行求解。当然了，记忆化搜索还是有很多有趣的题目的，我们会把它作为一个专题来说。在这一节我们先留个悬念。
BFS
Problem 8: Leetcode 958 给定一个二叉树，确定它是否是一个完全二叉树。 百度百科中对完全二叉树的定义如下： 若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）
从这一个题开始，我们来说一说与广度优先搜索（BFS）相关的内容。相比较深度优先搜索使用递归（栈）来完成搜索任务，广度优先搜索主要通过队列和迭代来完成。虽然最终两种方法都能够完成搜索任务，但是在实际的题目中，广度优先搜索还是在某些层面的问题上具有一点优势的。我们通过题目慢慢展开。
对于这一个问题，如果输入是[1,2,3,4,5,6]，那么它就是一棵完全二叉树，对应的树长这样。
如果要使用BFS，事实上类似树中的层序遍历。简单来说，我们并不是每一次枚举到一个元素就继续往下递归，而是每次遍历一个元素所相连的所有元素，然后把一层元素放到队列中，再按照这个放入的顺序一个一个访问，遍历，相连元素放入队列，以此类推直到全部遍历完。
对于这个问题，为什么BFS会更好呢？原因就在于，我们可以每一次遍历一层，这样遍历完之后就可以很快看出是否是完全二叉树（因为如果除了最后一层，有一层不是满的，那么就可以判定不是了）。DFS因为遍历顺序的问题，所以不一定能很快看到这一点。
好的，我们来看看代码。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
// 层序遍历的辅助利器
queue<TreeNode*> q;
// 记录是否已经遍历到null结果
bool reachNull = false;
q.push(root);
while (!q.empty())
{
TreeNode* curr = q.front();
q.pop();
if (curr == nullptr)
{
// 发现空结点了
reachNull = true;
continue;
}
else
{
// 发现null结点后出现非空结点，发现不完全了
if (reachNull)
{
return false;
}
// 继续遍历左右节点
q.push(curr->left);
q.push(curr->right);
}
}
return true;
}
};
代码的基本思路就是“一个空的节点之后依然还有其他的节点”，这个就说明最后一层上面的某一层并不是满的。同时对于最后一层，因为要求所有节点一定在左边，所以这个判断标准也是合适的。
Problem 9: Leetcode 210 现在你总共有 n 门课需要选，记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1] 给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。 可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
比方说输入是4, [[1,0],[2,0],[3,1],[3,2]]，那么输出就是[0,1,2,3] or [0,2,1,3]。对应的是下面这一张图。
这一道问题是极为经典的拓扑排序的问题。拓扑排序既是BFS的一个典型应用，也是《算法与数据结构》中的一个重要知识点，而且我还在面试中被问到过。所以我们这里把它拿出来说一说也好。
拓扑排序的目的就是，找到一种排列，使得
对于图
中的任意一条有向边
，
在排列中都出现在
的前面。
而这恰好就是这个题对于“合理的课程排列”的规定。而它的算法其实也很直接。
- 找到入度为0的所有点，进入队列。
- 对于每一个队列中的元素，移除与它相连的所有边，对应修改节点的入度，若有新的节点入度为0，则继续进入队列。
- 一直到队列清空，此时如果所有点已经遍历完成，则完成了拓扑排序。否则说明拓扑排序不存在。
思维简单，所以我们就直接放代码了。
class Solution {
private:
// 存储有向图
vector<vector<int>> edges;
// 存储每个节点的入度
vector<int> indeg;
// 存储答案
vector<int> result;
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses);
indeg.resize(numCourses);
for (const auto& info: prerequisites) {
edges[info[1]].push_back(info[0]);
++indeg[info[0]];
} // 建图
queue<int> q;
// 将所有入度为 0 的节点放入队列中
for (int i = 0; i < numCourses; ++i) {
if (indeg[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
// 从队首取出一个节点
int u = q.front();
q.pop();
// 放入答案中
result.push_back(u);
for (int v: edges[u]) {
--indeg[v];
// 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
if (indeg[v] == 0) {
q.push(v);
}
}
}
if (result.size() != numCourses) {
return {}; // 判断最后是否遍历完了所有节点
}
return result;
}
};
Problem 10: Leetcode 127 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列： 序列中第一个单词是 beginWord 。序列中最后一个单词是 endWord 。每次转换只能改变一个字母。转换过程中的中间单词必须是字典 wordList 中的单词。给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
比方说输入是beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]，那么输出就是5，因为它的一个最短的转换序列是"hit" -> "hot" -> "dot" -> "dog" -> "cog"。
这一个问题是很经典的最短路的问题。因为我们一，是要寻找一个“最短的”变换路径。二是我们一步一步的变换，是可以通过建图来具象化的。因此虽然这一个题是一个hard，但是算法也就几步。
- 建图，如果两个单词之间只差一个字母，那么就连一条边，边权为1。
- 从起点开始BFS，到达终点即说明找到了路径，将路径经过的长度取最小值即可。
非常标准的找最短路的步骤。
但是这里有一个细节。就是怎么建图。这一个题是一个hard，所以不可能这个方法就让你通过的。注意到建图这一步我们如果用现在的方法，时间复杂度就是
（如果我们设单词列表长度为
的话），这很明显是一个很高的复杂度。那么有没有优化的方法呢？
答案当然是有的，就是考虑虚拟节点的解法。具体来说，我们考虑的是，对于每一个单词（例如dog），都设置几个虚拟节点，将它的每一个字母都换成'*'（所以会换成3个节点，"*og", "d*g", "do*"。因为如果两个单词中间只差一个字母，那么它们一定会连接到同一个虚拟节点上。具体可以看下图。
但是这样的话，对应的距离长度就会有改变，这一点也在代码中有所体现。
好的，我们来看看代码吧。
class Solution {
public:
unordered_map<string, int> wordId;
vector<vector<int>> edge;
int nodeNum = 0;
void addWord(string& word) {
if (!wordId.count(word)) {
wordId[word] = nodeNum++;
edge.emplace_back();
}
}
void addEdge(string& word) { // 创建虚拟节点并连上边
addWord(word);
int id1 = wordId[word];
for (char& it : word) {
char tmp = it;
it = '*';
addWord(word); // 注意这一步，循环的时候it是带引用的，换句话说上一步的it修改是会影响到下一步的word的。
int id2 = wordId[word];
edge[id1].push_back(id2);
edge[id2].push_back(id1);
it = tmp;
}
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
for (string& word : wordList) {
addEdge(word);
}
addEdge(beginWord);
if (!wordId.count(endWord)) { // 没有找到endWord
return 0;
}
vector<int> dis(nodeNum, INT_MAX);
int beginId = wordId[beginWord], endId = wordId[endWord];
dis[beginId] = 0;
queue<int> que;
que.push(beginId);
while (!que.empty()) {
int x = que.front();
que.pop();
if (x == endId) {
return dis[endId] / 2 + 1; // 虚拟节点会将距离变成2倍，同时因为没有一开始起点的贡献（起点并没有考虑添加虚拟节点），所以要+1
}
for (int& it : edge[x]) {
if (dis[it] == INT_MAX) {
dis[it] = dis[x] + 1;
que.push(it);
}
}
}
return 0;
}
};
读者可能可以发现的一点是，这里虽然要求是“最短路径”，但是全程都没有出现过求min的步骤。读者可以结合BFS的特点，想想这是为什么？以及如果边权不是1，而是其他的可变的数字，这里是不是还可以这么写？
当然了，最短路问题的Dijstkra算法，也是一个必须要掌握的算法。虽然这里没有给出具体的题目，但是我们依然推荐大家去复习一下这个算法的代码，以防万一。
小结
本节我们列举了一些传统的使用DFS和BFS求解的问题。需要注意的是这些问题多半都和“选择不选择”，递归，图形的遍历等有关系，解法往往也比较直接。当然，有的题在筛选的时候有一些技巧，读者也应该多做考量。
下一节我们来讲一下记忆化搜索，和一些树有关的问题。树的结构千奇百怪，与它结合的有趣的习题也很多，相信这也会是比较硬核的一节hh。