LeetCode 79. 单词搜索——DFS回溯与原地标记的空间优化

适读人群：Java初中级工程师、算法进阶者 | 阅读时长：约22分钟 | 难度：中等

---

开篇故事

单词搜索是一道特别适合练习二维网格回溯的题目。它把"路径搜索"和"状态回溯"结合在了一起，不像之前那些回溯题有明确的"每层选一个数"的模式，而是在二维网格上四方向扩展，且要防止重复访问同一格。

这道题有一个特别优雅的空间优化：用"临时标记"代替 visited 数组。将访问过的格子原地修改（标记为非字母字符如 #），DFS 结束后恢复原来的字符。这样省去了 O(m×n) 的 visited 数组，只用 O(1) 额外空间（不含递归栈）。

很多题解直接给出原地标记的版本，但没有解释清楚"为什么这样做是线程安全的"——在多线程环境下这当然不安全，但在单线程回溯中，每次进入和退出 DFS 时格子都会被正确恢复，所以整体是正确的。今天我们从有 visited 数组的版本入手，一步步优化到原地标记的最终版本。

---

一、题目解析

题目： 给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中"相邻"单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例：

• board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"，输出：true
• board = [...], word = "SEE"，输出：true
• board = [...], word = "ABCB"，输出：false（B 不能重复用）

回溯框架：

1. 枚举所有可能的起始格子（与 word[0] 相同的格子）。
2. 从起始格子开始 DFS，每次向四个方向扩展，匹配 word 的下一个字符。
3. 已访问的格子不能再次使用（避免重复）。
4. 若某路径失败，回溯恢复状态。

---

二、解法一：DFS + visited 数组（清晰版）

代码

public class Solution_Visited {
    private int m, n;
    private boolean[][] visited;
    private int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (board[r][c] == word.charAt(0)) {
                    visited[r][c] = true;
                    if (dfs(board, word, r, c, 1)) return true;
                    visited[r][c] = false;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int r, int c, int idx) {
        if (idx == word.length()) return true; // 所有字符都匹配
        
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n 
                && !visited[nr][nc] && board[nr][nc] == word.charAt(idx)) {
                visited[nr][nc] = true;
                if (dfs(board, word, nr, nc, idx + 1)) return true;
                visited[nr][nc] = false;
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度： O(m×n × 4^L)，其中 L = word.length()。对每个格子作为起点，DFS 最多走 4^L 条路径（每步4个方向）。
• 空间复杂度： O(m×n) visited 数组 + O(L) 递归栈。

---

三、解法二：DFS + 原地标记（空间优化版）

思路

将 visited[r][c] = true 替换为 board[r][c] = '#'（或其他非字母字符），回溯时恢复 board[r][c] = word.charAt(idx-1)（或恢复原来的字符）。

正确性分析：

原地标记的正确性依赖于回溯的"对称性"：

• 进入格子 (r,c) 时：将其标记为 #（不可再访问）。
• 递归处理邻居节点。
• 退出格子 (r,c) 时：将其恢复为原来的字符。

由于 DFS 是深度优先的，在当前路径的任何时刻，# 标记的格子恰好是"当前路径上已访问的格子"。当一个分支失败时，回溯恢复了所有修改，其他分支不受影响。

代码

public class Solution {
    private int m, n;
    private int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (dfs(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int r, int c, int idx) {
        // 边界检查 + 字符匹配
        if (r < 0 || r >= m || c < 0 || c >= n) return false;
        if (board[r][c] != word.charAt(idx)) return false;
        
        // 所有字符都匹配
        if (idx == word.length() - 1) return true;
        
        // 原地标记：将当前格子设为 '#'，防止当前路径重复访问
        char original = board[r][c];
        board[r][c] = '#';
        
        // 向四个方向搜索
        boolean found = dfs(board, word, r+1, c, idx+1)
                     || dfs(board, word, r-1, c, idx+1)
                     || dfs(board, word, r, c+1, idx+1)
                     || dfs(board, word, r, c-1, idx+1);
        
        // 恢复原来的字符（回溯）
        board[r][c] = original;
        
        return found;
    }
}

Mermaid 图：原地标记的回溯过程

复杂度分析

• 时间复杂度： O(m×n × 4^L)，与解法一相同。
• 空间复杂度： O(L) 递归栈，无需 visited 数组（O(m×n) 的空间节省）。

---

四、解法三：剪枝优化

思路

在遍历网格前，先检查字符频率：如果 word 中某个字符在 board 中出现次数不够，直接返回 false。

另一个剪枝：从 word 的较短端开始搜索。如果 word 的最后一个字符在 board 中出现次数更少，可以反转 word，从频率更少的端开始搜索（搜索空间更小）。

public class Solution_Pruned {
    // ...（框架与解法二相同）
    
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        
        // 剪枝1：字符频率检查
        int[] charCount = new int[128];
        for (char[] row : board) for (char c : row) charCount[c]++;
        for (char c : word.toCharArray()) {
            if (--charCount[c] < 0) return false; // board 中某字符不够用
        }
        
        // 剪枝2：选择频率更少的端开始搜索
        // （比较 word 首字符和尾字符在 board 中的频率，选频率小的端开始）
        // 这里省略实现，思路是若word末尾字符更稀少，则翻转word
        
        // 主体与解法二相同
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (dfs(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int r, int c, int idx) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return false;
        if (board[r][c] != word.charAt(idx)) return false;
        if (idx == word.length() - 1) return true;
        char orig = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, word, r+1, c, idx+1) || dfs(board, word, r-1, c, idx+1)
                     || dfs(board, word, r, c+1, idx+1) || dfs(board, word, r, c-1, idx+1);
        board[r][c] = orig;
        return found;
    }
}

---

五、举一反三

二维网格 DFS 回溯模板

// 通用的二维网格 DFS 回溯模板
private int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

private boolean dfs(char[][] grid, ..., int r, int c, int state) {
    // 边界检查
    if (r < 0 || r >= m || c < 0 || c >= n) return false;
    // 条件检查（字符匹配、是否已访问等）
    if (!满足条件(grid[r][c], state)) return false;
    // 终止条件
    if (达到目标) return true;
    
    // 标记访问（原地或visited数组）
    char orig = grid[r][c];
    grid[r][c] = '#';
    
    // 递归四方向
    boolean result = false;
    for (int[] d : dirs) {
        result = dfs(grid, ..., r+d[0], c+d[1], nextState);
        if (result) break; // 找到就停止（若只需找存在性）
    }
    
    // 回溯
    grid[r][c] = orig;
    return result;
}

相关题目

• LeetCode 200. 岛屿数量：DFS 计数，不需要回溯（已访问的格子设为'0'即可，无需恢复）。
• LeetCode 212. 单词搜索 II（下一篇）：多单词搜索，用 Trie 优化。

---

六、踩坑实录

坑一：恢复字符时用原字符而不是 word 中的字符

// 错误：恢复为 word[idx]，而实际上 board[r][c] 可能与 word[idx] 不同
// （虽然我们检查了相等，但原字符是 board 的原始值，应该用 original 变量保存）
board[r][c] = word.charAt(idx); // 如果 board[r][c] 原来就是 word[idx] 这是对的，但用 orig 更安全

// 正确：保存原字符，回溯时恢复
char original = board[r][c];
board[r][c] = '#';
// ...递归...
board[r][c] = original;

虽然在本题中 board[r][c] == word.charAt(idx)（因为我们先检查了相等才进入），所以直接用 word.charAt(idx) 也对，但用 original 更通用和安全，养成好习惯。

坑二：搜索提前返回时 board 未恢复

如果用短路求值 || 连接四个方向，当某个方向找到结果后会直接返回 true，不执行后续方向，也不会执行回溯（board[r][c] = original 这行不会被执行）！

在本题中这是对的，因为 exist 只需返回布尔值，找到后直接结束，不需要继续搜索，board 的状态在函数返回后也不会被外部使用（递归展开后自然清空）。

但如果是"找所有路径"的题目，就需要无论成功失败都要回溯，不能用短路求值 ||。

坑三：m 和 n 的方向

m = board.length（行数），n = board[0].length（列数）。检查边界时 r < m, c < n。行和列搞反是很常见的错误，要养成统一命名的习惯（r 行 row，c 列 column）。

---

七、总结

单词搜索展示了二维网格回溯的标准模式，核心是"访问标记"的两种实现：

1. visited 数组：代码清晰，不修改原始数据，但需要 O(m×n) 额外空间。
2. 原地标记：省去 visited 数组，空间更优，代码稍简洁，但修改了输入数据（通过回溯恢复）。

原地标记在面试中更受推崇，但要能清楚说明"为什么修改原始数组是安全的"（单线程回溯，每次进出都配对恢复）。

解法	时间复杂度	空间复杂度（不含递归栈）	推荐
DFS + visited 数组	O(m×n × 4^L)	O(m×n)	可接受
DFS + 原地标记	O(m×n × 4^L)	O(1)	推荐
DFS + 剪枝	O(m×n × 4^L)	O(1)	最优

---

补充深入讲解：网格DFS回溯的设计原则与空间优化

网格 DFS 与树形 DFS 的核心区别

普通树形 DFS（如决策树、排列树）每个节点有固定的子节点，不会重复访问已访问的节点（因为树没有环）。网格 DFS 的情况完全不同：网格是一个图，每个单元格最多有四个邻居，且图中有环（可以绕圈），必须通过"标记已访问"来避免重复访问。

在单词搜索中，路径必须不重叠（同一个单元格不能在同一条路径中被使用两次）。如果不标记已访问，会产生"在 (r,c) 处找下一个字符，又回到 (r,c) 自身"的循环，既产生错误结果，也可能导致无限递归。

visited 数组（额外 O(m×n) 空间）和原地标记（board[r][c] = '#'）是两种常见的标记方式。原地标记在回溯时还原（board[r][c] = word[i]），避免了额外空间，是空间优化的标准技巧。

原地标记的正确性保证

原地标记的关键在于正确的"做标记-递归-撤销标记"流程：

做标记：char tmp = board[r][c]; board[r][c] = '#'; 递归：递归调用 DFS 探索下一个字符。 撤销标记：board[r][c] = tmp;（不能写 board[r][c] = word[i]，因为 tmp 才是原始值）

为什么要用 tmp 保存原始值而不是直接写 board[r][c] = word[i]？在本题中，word[i] 就是原始值，写 word[i] 也是对的。但如果代码结构稍作修改（比如不传 index 而是直接传字符），就可能写错。养成保存 tmp 再还原的好习惯，可以避免一类潜在错误。

标记值必须是"不可能在单词中出现的字符"，即确保不会与合法字符混淆。题目保证 board 和 word 都只含大小写字母（A-Za-z），所以用 '#' 是安全的——不会与任何合法字符冲突。

剪枝策略：优化 DFS 效率

单词搜索的 DFS 有几个可以优化的剪枝点：

第一，越界和字符不匹配时立即返回。在每次递归的开头先检查 (r,c) 是否越界，以及 board[r][c] 是否等于 word[index]，不满足直接返回 false。这是最基本的剪枝，代码中都有体现。

第二，统计字符频率，快速排除不可能的输入。在正式 DFS 之前，统计 board 中每个字符的出现次数，与 word 中每个字符的需要次数对比。如果 board 中某个字符的出现次数少于 word 中需要的次数，直接返回 false，无需进行 DFS。这个预处理是 O(m×n + len(word)) 的，但能避免在明显无解的情况下进行昂贵的 DFS。

第三，正反向比较选择更稀有的起点。如果 word 的第一个字符在 board 中出现次数多，而最后一个字符出现次数少，考虑反向搜索（从 word 的最后一个字符开始）。出现次数越少的字符作为起点，DFS 分支数越少，整体速度越快。

时间复杂度的精确分析

单词搜索的时间复杂度分析比较复杂。设棋盘大小为 m×n，单词长度为 L。

最坏情况下（所有格子都是相同字符，单词也是相同字符），DFS 会探索每个格子作为起点，每次 DFS 探索所有 3^L 条路径（每步有最多 3 个候选方向，不回头）。总时间复杂度是 O(m×n×3^L)。

为什么是 3^L 而不是 4^L？因为每次移动来自某个方向，不会立刻回头（来的方向不算候选），所以每步最多有 3 个新方向，而不是 4 个。这个细节使得实际搜索空间是理论最坏情况的 (3/4)^L 倍，在 L 较大时差异显著。

在实际测试中，由于字符匹配失败的剪枝，绝大多数路径很快就被截断，实际运行时间远小于理论最坏情况。

DFS 标记技术的工程应用

原地标记然后还原的技术在工程中有广泛应用，不局限于字符网格。

在图的 DFS 中，"标记正在访问的节点"（用特殊状态，如 VISITING），"标记访问完成的节点"（如 VISITED），"还原为未访问"（如果需要枚举所有路径）是环检测和路径枚举的标准模式。

在游戏开发中，地图探索算法（Flood Fill、路径寻找）大量使用类似的标记策略，通常用一个临时的 visited 位数组（每个位置用 1 位表示），比二维布尔数组更节省空间，适合嵌入式系统。

在文本搜索和模式匹配中，DFS 遍历字典树（Trie）同时扫描输入文本，是多模式匹配的核心技术，下一道题（LeetCode 212 单词搜索 II）就是这个思路的应用。

---

单词搜索的边界条件处理

单词搜索（LeetCode 79）看似简单，但有几个边界条件值得关注。

第一，单词长度为 1 时（word 只有一个字符），只需检查棋盘中是否存在该字符，不需要 DFS 移动。代码中 DFS 的 index == word.length()-1 的判断能正确处理这种情况：当 index=0 且 word.length()=1 时，找到起点就直接返回 true。

第二，棋盘只有一个格子时（board.length1 && board[0].length1），只能匹配长度为 1 的单词。这种情况也能被标准代码正确处理，不需要特殊分支。

第三，当同一个字符在棋盘中出现很多次，但单词很长时，朴素实现会在很多起点重复进行昂贵的 DFS，性能较差。这时可以加入字符频率预检查：统计 board 中每个字符的出现次数，和 word 中所需次数对比，如果任何字符不足，提前返回 false。这个 O(m×n) 的预处理能在明显无解时避免昂贵的 DFS。

单词搜索与图遍历的关联

棋盘可以看作一个特殊的无向图：每个格子是节点，相邻的格子之间有边（上下左右四个方向）。单词搜索等价于：在这个图中，从某个字符等于 word[0] 的节点出发，能否找到一条长度为 len(word) 的路径，使得路径上第 k 个节点的字符等于 word[k]，且路径不重复经过同一节点？

这是图中的"带约束的简单路径查找"问题。在一般图中，这类问题是 NP 完全的（哈密顿路径问题是其特例）。但由于棋盘图的特殊结构（网格图，度最多为 4），配合单词长度的约束（路径长度 = 单词长度），实际上可以在可接受的时间内回溯求解。

理解了单词搜索与图遍历的关联，有助于将这道题的解法迁移到更一般的图路径搜索场景，是算法抽象能力的体现。在面试中，如果能从"图遍历"的角度解释单词搜索，展示了对问题本质的深层理解，往往能给面试官留下深刻印象。

单词搜索的常见面试变形

LeetCode 79 在面试中有几个常见变形，了解这些变形有助于展示算法的灵活应用能力。

变形一：字符可以斜向移动（8个方向而不是4个方向）。代码修改只需要将 dirs 数组从4个方向扩展到8个方向，其他逻辑不变。这是最简单的变形，用来测试候选人是否真正理解方向数组的作用，而不是死记硬背4个方向。

变形二：单词可以重复使用棋盘上的格子（取消不重叠约束）。这时不需要标记和还原，代码简化为普通的 DFS（但要注意终止条件，否则会无限递归）。通常加上"路径长度不超过单词长度"的限制。

变形三：棋盘是三维的（三维字母块），找路径。框架完全相同，只需将 dirs 从二维方向（4个）扩展到三维方向（6个，上下左右前后），DFS 框架不变。这个变形考查候选人是否能灵活地将二维框架推广到高维。

理解了这些变形，说明你对 DFS 框架的本质（方向数组、标记、递归）有清晰认识，不是只会做原题。

单词搜索与字符串类 DFS 的总结

单词搜索（LeetCode 79）是字符串类 DFS 的核心代表，核心要素是：起点枚举（每个格子作为起点）、路径标记（避免重复使用）、字符匹配（DFS 过程中逐字符比较）、状态还原（回溯时恢复标记）。这四个要素是网格字符串搜索的通用模板。

下一道题（LeetCode 212 单词搜索 II）在此基础上加入了 Trie，将单模式搜索升级为多模式搜索。从 79 到 212，是"单问题 DFS"到"多问题 Trie+DFS"的自然演进。两道题一起学，能完整掌握网格字符串搜索的全套技术栈。