一、题目背景LeetCode 79「单词搜索」是一道经典的二维网格搜索问题。题目给定一个m x n的字符网格board以及一个字符串word要求判断word是否能够在网格中被搜索出来。搜索规则如下单词必须按照字符顺序依次匹配每一步只能向上下左右四个方向移动同一个单元格不能在一次搜索路径中被重复使用如果存在一条合法路径可以构成word返回true否则返回false。例如board [ [A,B,C,E], [S,F,C,S], [A,D,E,E] ] word ABCCED可以从左上角的A出发A - B - C - C - E - D因此返回true。二、问题本质在二维网格中寻找一条合法路径这道题的本质不是简单的字符串匹配而是在二维网格中寻找一条长度为word.length()的路径使路径上的字符依次等于word中的字符。由于路径每一步有最多 4 个方向可以选择所以天然适合使用深度优先搜索 DFS。同时由于每个格子在一条路径中不能重复使用所以搜索过程中还需要维护访问状态并在搜索失败时撤销选择。这正是典型的回溯算法。三、为什么使用 DFS 回溯假设我们当前要匹配word[index]并且当前位置是(row, col)。如果board[row][col] word[index]说明当前位置字符匹配成功。接下来我们需要继续匹配word[index 1]这个字符只能从当前位置的上下左右四个相邻格子中寻找。因此搜索逻辑可以抽象为当前位置匹配成功 标记当前位置已经使用 向上下左右继续搜索下一个字符 如果某个方向成功返回 true 如果四个方向都失败撤销当前位置标记 返回 false这就是 DFS 回溯的核心框架。四、回溯过程分析以word ABCCED为例。从(0, 0)的A开始A匹配成功继续找B。向右到(0, 1)A - B匹配成功继续找C。向右到(0, 2)A - B - C继续找下一个C。向下到(1, 2)A - B - C - C继续找E。向下到(2, 2)A - B - C - C - E继续找D。向左到(2, 1)A - B - C - C - E - D全部匹配成功返回true。如果某一步发现四个方向都走不通就需要回退到上一个位置尝试其他方向。这就是“回溯”的含义。五、关键问题如何避免重复使用同一个格子题目要求同一个单元格内的字母不允许被重复使用。常见做法有两种方法一使用 visited 数组定义vectorvectorbool visited;当某个位置被访问时将其标记为true。搜索结束后再恢复为false。方法二原地修改 board由于board中只包含大小写英文字母所以可以临时把访问过的位置改成特殊字符例如#。搜索结束后再恢复原字符。例如char temp board[row][col]; board[row][col] #; // 搜索四个方向 board[row][col] temp;这种方式可以避免额外的visited数组空间更优。六、基础版代码实现#include vector #include string using namespace std; class Solution { public: bool exist(vectorvectorchar board, string word) { int m board.size(); int n board[0].size(); for (int i 0; i m; i) { for (int j 0; j n; j) { if (dfs(board, word, i, j, 0)) { return true; } } } return false; } private: bool dfs(vectorvectorchar board, string word, int row, int col, int index) { int m board.size(); int n board[0].size(); if (row 0 || row m || col 0 || col n) { return false; } if (board[row][col] ! word[index]) { return false; } if (index word.size() - 1) { return true; } char temp board[row][col]; board[row][col] #; bool found dfs(board, word, row 1, col, index 1) || dfs(board, word, row - 1, col, index 1) || dfs(board, word, row, col 1, index 1) || dfs(board, word, row, col - 1, index 1); board[row][col] temp; return found; } };七、代码逻辑拆解1. 枚举起点for (int i 0; i m; i) { for (int j 0; j n; j) { if (dfs(board, word, i, j, 0)) { return true; } } }因为单词可能从任意位置开始所以需要遍历整个网格把每一个格子都作为起点尝试搜索。2. 越界判断if (row 0 || row m || col 0 || col n) { return false; }如果当前位置超出网格范围说明路径不合法。3. 字符匹配判断if (board[row][col] ! word[index]) { return false; }如果当前位置字符与当前需要匹配的字符不同直接剪枝。4. 递归终止条件if (index word.size() - 1) { return true; }如果已经匹配到单词最后一个字符并且当前字符也匹配成功说明整个单词已经找到。5. 标记当前位置char temp board[row][col]; board[row][col] #;将当前位置临时标记为#防止后续搜索又走回这个格子。6. 搜索四个方向bool found dfs(board, word, row 1, col, index 1) || dfs(board, word, row - 1, col, index 1) || dfs(board, word, row, col 1, index 1) || dfs(board, word, row, col - 1, index 1);只要上下左右任意一个方向可以成功匹配剩余字符就说明当前路径有效。7. 恢复现场board[row][col] temp;这是回溯算法中非常关键的一步。因为当前路径搜索结束后其他路径仍然可能需要使用这个格子所以必须恢复原字符。如果不恢复后续搜索结果会被污染。八、进阶优化搜索剪枝题目进阶要求我们使用剪枝优化搜索效率。虽然本题数据范围较小m, n 6 word.length 15但是从算法设计角度来看剪枝非常重要。剪枝一如果 word 长度大于网格格子数直接返回 false如果单词长度超过网格总格子数一定无法构造成功。if (word.size() m * n) { return false; }剪枝二统计字符频率如果word中某个字符出现次数比board中该字符出现次数还多那么一定无法匹配。例如board 中只有 1 个 A word 中需要 3 个 A这种情况不需要 DFS直接返回false。剪枝三从更稀有的字符开始搜索如果word的首字符在网格中出现很多次而尾字符出现很少次那么从首字符开始会产生很多无效分支。例如word AAAAAZ如果A很多Z很少那么从A开始会尝试大量路径。由于单词路径可以反向搜索所以可以将word反转从更稀有的一端开始匹配。if (count[word[0]] count[word[word.size() - 1]]) { reverse(word.begin(), word.end()); }这个优化在大网格中非常有效。九、优化版代码实现#include vector #include string #include algorithm using namespace std; class Solution { public: bool exist(vectorvectorchar board, string word) { int m board.size(); int n board[0].size(); if (word.size() m * n) { return false; } vectorint count(128, 0); for (int i 0; i m; i) { for (int j 0; j n; j) { count[board[i][j]]; } } for (char c : word) { count[c]--; if (count[c] 0) { return false; } } for (int i 0; i m; i) { for (int j 0; j n; j) { count[board[i][j]]; } } if (count[word[0]] count[word[word.size() - 1]]) { reverse(word.begin(), word.end()); } for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] word[0]) { if (dfs(board, word, i, j, 0)) { return true; } } } } return false; } private: int dirs[4][2] { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; bool dfs(vectorvectorchar board, string word, int row, int col, int index) { if (board[row][col] ! word[index]) { return false; } if (index word.size() - 1) { return true; } int m board.size(); int n board[0].size(); char temp board[row][col]; board[row][col] #; for (int i 0; i 4; i) { int nextRow row dirs[i][0]; int nextCol col dirs[i][1]; if (nextRow 0 || nextRow m || nextCol 0 || nextCol n) { continue; } if (board[nextRow][nextCol] #) { continue; } if (dfs(board, word, nextRow, nextCol, index 1)) { board[row][col] temp; return true; } } board[row][col] temp; return false; } };十、优化版代码说明优化版代码主要做了三件事。1. 长度剪枝if (word.size() m * n) { return false; }如果单词长度超过格子总数必然无法搜索成功。2. 频率剪枝for (char c : word) { count[c]--; if (count[c] 0) { return false; } }如果word中需要的某个字符数量超过网格中该字符数量直接返回false。这类剪枝属于搜索前预处理可以大幅减少无意义 DFS。3. 起点方向优化if (count[word[0]] count[word[word.size() - 1]]) { reverse(word.begin(), word.end()); }如果单词首字符出现次数比尾字符多那么从尾字符开始搜索分支更少。例如word AAAAAB假如A有很多B很少那么反转成BAAAAA从B开始搜索可以显著降低起点数量。十一、复杂度分析设m board 的行数 n board 的列数 L word 的长度时间复杂度最坏情况下每个格子都可能作为起点。第一个字符之后每一步最多向 3 个方向扩展因为不能立刻回到上一个格子。所以时间复杂度可以近似表示为O(m * n * 3^L)严格来说第一步最多有 4 个方向后续由于访问限制分支数会下降。空间复杂度如果使用原地修改board不额外使用visited数组。递归深度最多为L因此空间复杂度为O(L)这部分空间来自递归调用栈。十二、为什么不是 BFS这道题也可以从搜索角度理解为路径查找问题但并不适合 BFS。原因是每一条路径都有独立的访问状态同一个格子不能在同一路径中重复使用BFS 需要存储大量路径状态空间开销较大DFS 天然适合“走一条路径不行再回退”的搜索模型。因此本题最自然的解法是DFS 回溯而不是 BFS。十三、常见错误总结错误一忘记恢复现场错误写法board[row][col] #; // 搜索结束后没有恢复这样会导致其他搜索路径无法正常使用该格子。正确写法char temp board[row][col]; board[row][col] #; // DFS board[row][col] temp;错误二没有处理越界搜索上下左右时必须判断边界否则会访问非法数组下标。错误三重复使用同一个格子如果不做访问标记可能出现如下非法路径A - B - A其中同一个A被使用了多次。错误四递归终止条件写错很多人会把终止条件写成if (index word.size()) return true;这种写法也可以但需要配合不同的递归设计。在本文代码中当前层负责匹配word[index]所以终止条件是if (index word.size() - 1) { return true; }含义是当前字符已经是最后一个字符并且已经匹配成功。十四、总结LeetCode 79「单词搜索」是一道典型的二维网格 DFS 回溯题。它的核心思想可以概括为枚举每一个起点 从起点开始 DFS 每次匹配当前字符 向上下左右搜索下一个字符 使用标记防止重复访问 搜索失败后恢复现场这道题考查的不只是 DFS更重要的是对“状态”的理解。在回溯算法中每一步选择都会改变当前路径状态当这条路径失败时必须撤销选择让其他路径继续搜索。因此本题的关键不是简单地“递归四个方向”而是在搜索过程中正确维护路径状态并在回溯时恢复现场。最终推荐解法是DFS 回溯 原地标记 字符频率剪枝 起点方向优化这套写法既清晰也具备较好的性能表现。
