10 搜索算法面试通关：模式识别与优化策略总结

搜索算法面试通关：模式识别、选型决策与高频陷阱

摘要

本文是搜索算法专栏的终章，不讲新题，而是从更高的视角梳理整个专栏的核心脉络：如何从题目描述快速判断该用 BFS 还是 DFS？回溯的三要素如何快速提炼？哪些错误在面试中出现频率最高？记忆化搜索与 DP 之间如何切换？带着这些问题复习，能让前九篇的所有知识在脑中形成结构化的知识网络，真正达到”面试通关”的效果。

---

第 1 章 算法选型决策树

1.1 第一步：识别问题类型

面试题来了，首先问自己：

这道题的本质是什么？
├─ 在图/矩阵/隐式图上找路径或状态 → 搜索类
├─ 枚举满足条件的所有方案 → 回溯类
└─ 只是遍历整个状态空间 → 可能是 BFS/DFS 或 DP

搜索类题目的典型关键词：

• “最短路径”、“最少步数”、“最少变换次数” → BFS
• “是否存在路径”、“能否到达” → BFS 或 DFS 均可（BFS 更适合无权图）
• “所有路径”、“所有方案” → DFS + 回溯
• “在矩阵中找连通区域” → DFS（Flood Fill）或 BFS

回溯类题目的典型关键词：

• “所有组合”、“所有排列”、“所有子集”
• “所有可能的分割”、“所有合法方案”
• “找满足条件的所有解”（N-Queens、Sudoku 的所有解）

1.2 第二步：BFS vs DFS 精细决策

确认是搜索类问题后，做更精细的判断：

需要最短路径（边权相等）？
├─ 是 → BFS（天然按层扩展，第一次到达即最短）
└─ 否 → 继续判断

需要找所有路径，或路径数量非常多？
├─ 是 → DFS + 回溯（BFS 存所有路径内存爆炸）
└─ 否 → 继续判断

状态空间树的深度已知、有限？
├─ 深度很深（可能无限） → BFS（用队列，按层控制）
└─ 深度有限 → DFS 通常更简洁

搜索空间接近于树（无回路）？
├─ 是 → DFS（无需 visited，递归更清晰）
└─ 否（是图） → BFS/DFS 都需要 visited

核心判据

最短路 → BFS；枚举所有解 → DFS；其他情况两者均可，选代码更简洁的那个。

1.3 第三步：回溯三要素

确认要用 DFS + 回溯后，立即明确三个要素：

1. 选择列表（在当前节点可以做哪些选择？）
   - 组合题：从 start 到末尾的所有元素
   - 排列题：未使用的所有元素
   - 字符串分割：当前位置之后的所有切割点
   - 棋盘：当前行/格子的所有合法位置

2. 路径（当前已做的选择序列）
   - 通常用 List<T> path 或 StringBuilder sb
   - 棋盘题可以直接用 int[] queens / char[][] board

3. 终止条件（何时生成一个结果/停止递归？）
   - 路径长度达到目标
   - 目标索引 == 输入长度
   - 棋盘所有行/格子填满

---

第 2 章 各题型的代码框架速记

2.1 BFS 标准框架

// 适用：最短路径、最少变换步数
int bfs(State start, State target) {
    Queue<State> queue = new LinkedList<>();
    Set<State> visited = new HashSet<>();
    queue.offer(start);
    visited.add(start);
    int steps = 0;
 
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            State cur = queue.poll();
            if (cur.equals(target)) return steps;
            for (State next : getNeighbors(cur)) {
                if (!visited.contains(next)) {
                    visited.add(next);
                    queue.offer(next);
                }
            }
        }
        steps++;
    }
    return -1;  // 不可达
}

关键要点：

1. visited.add(start) 在入队时标记（不是出队时）
2. 用 size = queue.size() 控制层的边界
3. visited.add(next) 在入队前立即标记，防止重复入队

2.2 DFS / 回溯标准框架

// 适用：枚举所有方案（组合/排列/分割/棋盘）
void backtrack(输入, 当前位置/状态, 路径 path, 结果 result) {
    // 终止条件
    if (达到目标) {
        result.add(new ArrayList<>(path));  // 深拷贝！
        return;
    }
 
    for (每个可能的选择 choice : 选择列表) {
        if (不合法) continue;          // 剪枝
 
        path.add(choice);              // 做选择
        修改约束状态(choice);
 
        backtrack(输入, 下一位置, path, result);  // 递归
 
        path.remove(path.size()-1);    // 撤销选择
        恢复约束状态(choice);
    }
}

关键要点：

1. 添加到 result 时必须深拷贝（new ArrayList<>(path)）
2. 做选择和撤销选择必须对称（修改了什么就恢复什么）
3. 剪枝 continue 放在”做选择”之前

2.3 矩阵 DFS（Flood Fill vs 路径搜索）

// Flood Fill：永久标记，不撤销
void dfs(char[][] grid, int i, int j) {
    if (越界 || 不满足条件) return;
    grid[i][j] = '#';  // 永久标记
    for (int[] d : new int[][]{{1,0},{-1,0},{0,1},{0,-1}}) {
        dfs(grid, i+d[0], j+d[1]);
    }
    // 没有撤销！
}
 
// 路径搜索：临时标记，有撤销
boolean dfs(char[][] board, int i, int j, String word, int k) {
    if (k == word.length()) return true;
    if (越界 || board[i][j] != word.charAt(k)) return false;
    char tmp = board[i][j]; board[i][j] = '#';  // 临时标记
    boolean found = 四个方向的递归;
    board[i][j] = tmp;  // 撤销
    return found;
}

---

第 3 章 高频错误盘点

3.1 错误一：BFS 的 visited 标记时机错误

错误：出队时才标记 visited（而不是入队时）

后果：同一个状态被多次入队，队列膨胀，时间复杂度从 $O(V+E)$ 退化到 $O(V\cdot E)$ 甚至更差。

// 错误写法
while (!queue.isEmpty()) {
    State cur = queue.poll();
    visited.add(cur);  // ← 出队时才标记，太晚了！
    for (State next : getNeighbors(cur)) {
        if (!visited.contains(next)) {
            queue.offer(next);  // next 可能被多次入队
        }
    }
}
 
// 正确写法
visited.add(start);
while (!queue.isEmpty()) {
    State cur = queue.poll();
    for (State next : getNeighbors(cur)) {
        if (!visited.contains(next)) {
            visited.add(next);  // ← 入队前立即标记
            queue.offer(next);
        }
    }
}

3.2 错误二：回溯时忘记深拷贝

错误：直接将 path 引用加入 result

// 错误
result.add(path);  // path 是引用，后续修改会影响已存入的结果
 
// 正确
result.add(new ArrayList<>(path));  // 深拷贝

后果：result 中所有列表最终都变成最后一次 path 的状态（通常是空列表或最后一个有效组合）。

3.3 错误三：组合去重时 i > 0 与 i > start 的混淆

场景：Combination Sum II（元素有重复，每个只用一次）

// 错误：i > 0 会跳过当前层的某些合法选择
if (i > 0 && candidates[i] == candidates[i-1]) continue;
 
// 正确：只跳过当前层（start 之后）的重复元素
if (i > start && candidates[i] == candidates[i-1]) continue;

记忆方法：i > start 表示”在当前搜索层，如果前一个选择和当前选择相同，跳过”。i > 0 会错误地跳过”当前元素在前一层被用过但在当前层首次使用”的情况。

3.4 错误四：Word Search 忘记撤销 board[i][j]

char tmp = board[i][j]; board[i][j] = '#';
boolean res = dfs(...);
// 忘记 board[i][j] = tmp;
return res;

后果：格子被永久占用，后续从其他起点出发的路径无法使用该格子，产生 false negative。

3.5 错误五：N-Queens 对角线索引计算错误

错误：弄混主对角线和副对角线的公式

主对角线（\方向）：row - col = 常数 → 偏移后索引 = row - col + (n-1)
副对角线（/方向）：row + col = 常数 → 索引 = row + col（范围 [0, 2n-2]，无需偏移）

记忆方法：主对角线从左上到右下，row 和 col 同增同减（差值不变）；副对角线从右上到左下，row 增 col 减（和值不变）。

3.6 错误六：字符串回溯中 StringBuilder 的 delete 方法参数

// 错误：搞混 start/end 的含义
sb.delete(sb.length() - 1, sb.length());  // 正确，删除最后一个字符
 
// 或者用 setLength 更清晰
int prevLen = sb.length();
sb.append(s, i, j);  // 添加 [i, j) 子串
backtrack(...);
sb.setLength(prevLen);  // 恢复到添加前的长度

3.7 错误七：双向 BFS 中 visited 的更新时机

双向 BFS 中，不能在探索每个邻居时就把它加入 visited（会阻断另一侧的扩展）；必须完成整层扩展后，再将这层所有节点加入全局 visited。

// 错误：立即更新 visited（当前层的后续节点可能看不到上一层的标记）
for (String next : neighbors) {
    if (!visited.contains(next)) {
        visited.add(next);  // ← 太早了
        nextLayer.add(next);
    }
}
 
// 正确：完成整层后再更新
Set<String> nextLayer = new HashSet<>();
for (String cur : currentLayer) {
    for (String next : neighbors(cur)) {
        if (!visited.contains(next)) {
            nextLayer.add(next);
        }
    }
}
visited.addAll(currentLayer);  // 整层都探索完再标记

---

第 4 章 记忆化搜索与 DP 的关系

4.1 两者等价的条件

当 DFS 满足以下条件时，可以用记忆化替代重复计算（等价于 DP）：

1. 子问题重叠：同一个 (状态) 的返回值被计算多次
2. 无后效性：dfs(state) 的返回值只取决于 state，不受”如何到达 state”的影响

不适用记忆化的情况：回溯（需要枚举所有路径，子问题不共享），或者状态包含路径信息（如”已使用哪些元素”——使用集合表示，空间爆炸）。

4.2 转换方法

从 DFS 到记忆化 DFS：

// 第一步：识别递归函数的参数作为状态
int dfs(int i, int j) {
    // ...
}
 
// 第二步：创建 memo 数组/Map
Map<String, Integer> memo = new HashMap<>();
 
// 第三步：函数开头检查缓存，结尾存入缓存
int dfs(int i, int j) {
    String key = i + "," + j;
    if (memo.containsKey(key)) return memo.get(key);
    int res = ...;
    memo.put(key, res);
    return res;
}

从记忆化 DFS 到 DP：

// 自顶向下（记忆化 DFS）
int solve(int i, int j, int[][] memo) {
    if (i == 0 || j == 0) return 1;
    if (memo[i][j] != 0) return memo[i][j];
    return memo[i][j] = solve(i-1, j, memo) + solve(i, j-1, memo);
}
 
// 自底向上（DP）
int solve(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    return dp[m-1][n-1];
}

4.3 面试中如何回答”为什么不用 DP？”

当面试官对记忆化 DFS 或 DP 追问时，参考回答：

• 用记忆化 DFS（而非 DP）的理由：递归更直观，子问题的定义更自然；DP 需要确定状态转移方向（自底向上），记忆化 DFS 自动处理依赖关系。
• 用 DP（而非记忆化 DFS）的理由：DP 没有递归栈溢出的风险；对于路径计数问题，DP 状态含义清晰，工程实践中更常见。
• 两者时间复杂度相同：都是”状态数 × 每个状态的计算代价”。

---

第 5 章 专栏全局复杂度速查表

题目	算法	时间复杂度	空间复杂度
Word Ladder I (127)	BFS	$O(26\cdot n\cdot L^2)$	$O(n\cdot L)$
Word Ladder II (126)	BFS + DFS（路径还原）	$O(26\cdot n\cdot L^2)$	$O(n\cdot L)$
Number of Islands (200)	DFS/BFS	$O(mn)$	$O(mn)$
Flood Fill (733)	DFS	$O(mn)$	$O(mn)$
Pacific Atlantic (417)	反向 BFS	$O(mn)$	$O(mn)$
Combination Sum I (39)	回溯	$O(n^{T/M})$	$O(T/M)$
Combination Sum II (40)	回溯 + 去重	$O(2^n)$	$O(n)$
Palindrome Partitioning (131)	回溯 + DP 预处理	$O(n\cdot 2^n)$	$O(n^2)$
Generate Parentheses (22)	回溯	$O(C_n)$（第 n 个 Catalan 数）	$O(n)$
Restore IP Addresses (93)	回溯	$O(1)$（最多 $3^4$ 个节点）	$O(1)$
N-Queens (51)	回溯	$O(n!)$	$O(n)$
Sudoku Solver (37)	回溯	$O(9^{空格数})$（实际极快）	$O(1)$
Word Search (79)	DFS + 回溯	$O(mn\cdot 3^L)$	$O(L)$
Word Search II (212)	DFS + Trie	$O(mn\cdot 3^L+\sum len(w))$	$O(\sum len(w))$
Unique Paths (62)	DP / 记忆化 DFS	$O(mn)$	$O(mn)$

---

第 6 章 面试答题策略

6.1 开局（1-2 分钟）

1. 识别类型：BFS/DFS/回溯？（根据第 1 章决策树）
2. 说出关键词：例如”这道题要找最短路，用 BFS；用队列，按层扩展”
3. 定义状态：BFS 的节点是什么？DFS 的路径是什么？

6.2 设计阶段（2-3 分钟）

1. 回溯：说出三要素（选择、路径、终止条件）
2. BFS：确认 visited 结构和 step 计数方式
3. 复杂度：先说时间复杂度的上界，再说实际剪枝效果

6.3 编码阶段（10-15 分钟）

遵循以下顺序，降低犯错率：

1. 写函数签名（明确参数含义）
2. 写终止条件（base case）
3. 写主循环（做选择、递归、撤销）
4. 写剪枝条件（越界、约束检查）
5. 检查：visited 标记时机、深拷贝、撤销是否对称

6.4 常见追问及标准回答

“能做得更快吗？”

• BFS → 考虑双向 BFS（Word Ladder）
• 多词搜索 → 考虑 Trie 剪枝（Word Search II）
• 回溯 → 考虑更激进的剪枝（如提前检查剩余可能性）

“空间还能优化吗？”

• BFS 的 Set → 位运算或数组（当状态可以编码为整数时）
• DP 的二维数组 → 滚动数组（只保留上一行）

“有没有无法用回溯解决的情况？”

• 是的：当状态空间是图（有环）且需要统计路径数时，回溯可能无法收敛，需要记忆化 DFS 或 DP

---

第 7 章 专栏文章导图回顾

篇号	主题	核心知识点
01	BFS vs DFS 全景导览	状态空间抽象、适用边界
02	BFS 核心框架	Word Ladder I、层序扩展、隐式图
03	双向 BFS	Word Ladder II、前驱图、路径还原
04	DFS 与回溯核心框架	三要素、剪枝分类、Surrounded Regions
05	矩阵 BFS/DFS	连通分量、Flood Fill、多源 BFS
06	组合型回溯	Combination Sum、去重艺术
07	字符串型回溯	括号生成、回文分割、IP 恢复
08	棋盘型回溯	N-Queens 对角线公式、Sudoku 约束传播
09	矩阵路径搜索	Word Search、Trie 剪枝、Unique Paths
10	面试通关总结	选型决策树、高频错误、DP 桥梁

---

写在最后

搜索算法的核心，本质上是对状态空间的系统性遍历。BFS 用队列，按层展开，适合找最短路；DFS 用栈（或递归），深入探索，适合枚举所有解。回溯是 DFS + 撤销，让单条搜索路径可以被复用。

掌握搜索算法不在于背模板，而在于理解每种算法背后的”决策”：

• 为什么 BFS 能找最短路（而 DFS 不一定）？
• 为什么回溯必须撤销（而 Flood Fill 不需要）？
• 为什么去重条件是 i > start（而非 i > 0）？
• 为什么记忆化 DFS 和 DP 等价（而回溯不能记忆化）？

这些”为什么”想清楚了，面试时遇到变形题，才能临场推导出正确答案，而不是死套模板。

祝面试顺利！

---

关联文章：BFS 与 DFS 全景导览 | 矩阵深搜：Word Search 与路径问题 | 00 专栏导览