前言LeetCode 79 题「Word Search」要求给定一个二维字符网格和一个单词判断单词是否存在于网格中。单词必须按照字母顺序通过相邻的单元格上下左右构成同一个单元格内的字母不允许被重复使用。这是一道标准的二维网格回溯backtracking题也是理解「搜索 恢复现场」的入门题。初学者常犯的错误有三类。第一找到一条路径后忘记把标记恢复导致后续搜索被污染第二把「不能重复使用同一个单元格」误解为「不能走回头路」于是漏掉合法的折返路径第三递归函数里先访问board[i][j]再判断下标是否越界造成越界访问。本文按「建模 → 状态设计 → 剪枝 → 完整实现」的顺序讲清楚并给出复杂度分析。代码以 C17 为基准使用std::vectorstd::vectorchar表示网格。一、问题建模把网格看成一张图每个单元格是一个顶点上下左右相邻的单元格之间有一条无向边。问题变成是否存在一条长度等于单词长度的简单路径顶点不重复使得路径上的字符依次等于单词的字符。这个描述里有两个约束相邻每一步只能走到上下左右四个方向之一不能走对角线。不重复同一条路径上每个单元格最多使用一次。注意这是「路径内不重复」不是「全局只能访问一次」——不同的搜索分支可以访问同一个单元格只要它们不在同一条路径上。第二条是回溯的关键。如果用一个全局的visited数组并且找到后不恢复那么第一个分支走过的格子会永久封锁后续分支就无法使用答案会偏小。二、DFS 的状态与回溯定义递归函数dfs(i, j, k)当前位于单元格(i, j)已经匹配到单词的第k个字符返回是否能从当前位置继续匹配完整个单词。状态转移若k word.size()说明所有字符都匹配完了返回true。若(i, j)越界返回false。若(i, j)已被当前路径访问或board[i][j] ! word[k]返回false。标记(i, j)已访问。依次尝试四个方向只要有一个方向返回true就恢复标记并返回true。四个方向都失败恢复标记返回false。第 5、6 步的「恢复标记」就是回溯backtracking的核心进入一个分支前改变状态离开时把状态改回去保证兄弟分支看到的是进入前的世界。// 适用于 C17bool dfs(const std::vectorstd::vectorchar board,const std::string word,std::vectorstd::vectorbool visited,int i, int j, int k) {if (k static_castint(word.size())) return true;const int rows static_castint(board.size());const int cols static_castint(board[0].size());if (i 0 || i rows || j 0 || j cols) return false;if (visited[i][j]) return false;if (board[i][j] ! word[k]) return false;visited[i][j] true;static const int di[4] {1, -1, 0, 0};static const int dj[4] {0, 0, 1, -1};for (int d 0; d 4; d) {if (dfs(board, word, visited, i di[d], j dj[d], k 1)) {visited[i][j] false; // 恢复现场再返回return true;}}visited[i][j] false; // 回溯return false;}这里把边界检查放在访问board[i][j]之前顺序不能反。board[0].size()的前提是board非空所以调用方要先保证网格至少有一行一列这一点在完整代码里处理。另一种常见写法是原地修改board把访问过的字符改成特殊标记如#回溯时再改回来。这样省掉了visited数组空间从 O(m·n) 降到 O(L)L 是单词长度即递归深度。但它要求特殊标记不在单词字符集中否则会误判。用#时如果单词里真的包含#就会出错。稳妥起见本文用独立的visited数组如果确定字符集是大小写字母原地标记也可以。三、剪枝与复杂度最基础的剪枝是字符计数如果单词中某个字符出现的次数超过网格中该字符的总数直接返回false。这个检查是 O(m·n L)相对于搜索本身可以忽略。// 适用于 C17#include arraybool enough_chars(const std::vectorstd::vectorchar board,const std::string word) {std::arrayint, 256 need{};std::arrayint, 256 have{};for (char c : word) need[static_castunsigned char(c)];for (const auto row : board) {for (char c : row) have[static_castunsigned char(c)];}for (int c 0; c 256; c) {if (need[c] have[c]) return false;}return true;}这里用static_castunsigned char(c)做下标因为char是否有符号是实现定义的直接拿负值做数组下标是越界访问属于未定义行为undefined behavior, UB。复杂度方面最坏情况下每个单元格都作为起点每一步有 4 个方向实际第一个之后最多 3 个因为不能立刻回头搜索树的大小是 O(m·n·4^L)其中 L 是单词长度。这是一个很松的上界实际会因为字符不匹配和visited大幅剪枝。空间复杂度是 O(m·n)visited加上 O(L)递归栈。项目复杂度说明时间O(m·n·4^L) 上界L 为单词长度空间O(m·n L)visited 数组 递归栈字符预检O(m·n L)可提前排除不可能的输入四、完整实现// 适用于 C17#include iostream#include string#include vectorclass Solution {public:bool exist(std::vectorstd::vectorchar board, const std::string word) {if (word.empty()) return true;if (board.empty() || board[0].empty()) return false;rows_ static_castint(board.size());cols_ static_castint(board[0].size());visited_.assign(rows_, std::vectorbool(cols_, false));for (int i 0; i rows_; i) {for (int j 0; j cols_; j) {if (dfs(board, word, i, j, 0)) return true;}}return false;}private:bool dfs(const std::vectorstd::vectorchar board,const std::string word, int i, int j, int k) {if (k static_castint(word.size())) return true;if (i 0 || i rows_ || j 0 || j cols_) return false;if (visited_[i][j]) return false;if (board[i][j] ! word[k]) return false;visited_[i][j] true;static const int di[4] {1, -1, 0, 0};static const int dj[4] {0, 0, 1, -1};for (int d 0; d 4; d) {if (dfs(board, word, i di[d], j dj[d], k 1)) {visited_[i][j] false;return true;}}visited_[i][j] false;return false;}int rows_ 0;int cols_ 0;std::vectorstd::vectorbool visited_;};int main() {std::vectorstd::vectorchar board{{A, B, C, E},{S, F, C, S},{A, D, E, E}};Solution sol;std::cout std::boolalpha;std::cout sol.exist(board, ABCCED) \n; // 按标准语义应为 truestd::cout sol.exist(board, SEE) \n; // truestd::cout sol.exist(board, ABCB) \n; // falsereturn 0;}手工推演ABCCED从(0,0)的A出发向右到B向右到C向下到C向左到E向下到D路径合法且不重复。ABCB需要A→B→C→B但B已经被用过visited会拒绝四个方向都失败后回溯最终返回false。五、关于「不能重复使用」的两个细节第一visited是路径级别的不是全局的。同一个单元格可以在「以(0,0)为起点失败后以(1,1)为起点」的搜索中被重新使用。这就是为什么每次dfs返回前必须把visited_[i][j]恢复为false。第二不要用「不走回头路」来代替visited。比如只禁止「下一步走回上一步的格子」会漏掉形如A→B→A的合法路径如果单词是ABA且网格里有两个相邻的A。visited记录的是整条路径语义更准确。常见坑点1. 找到结果后不恢复 visited❌if (dfs(...)) return true;直接返回visited_[i][j]仍为true。✅ 返回前先visited_[i][j] false;或者用 RAII 风格的守卫对象自动恢复。2. 先访问 board 再判越界❌if (board[i][j] ! word[k]) return false;写在边界检查之前。✅ 先判断i、j的范围再访问数组。3. 网格为空时访问 board[0]❌cols_ board[0].size();对空board是越界。✅ 先判断board.empty()再取列数。4. 用全局 visited 且不回溯❌ 把visited当成「整个搜索只访问一次」的标记。✅ 明确它是「当前路径」的标记进入置位、离开复位。5. 原地标记用了单词里可能出现的字符❌ 用#标记但单词本身包含#导致误判。✅ 用独立的bool数组或选一个确定不在字符集中的标记。6. 忘记单词为空的情况❌ 空单词直接进入搜索k 0时立刻返回true其实没问题但有些实现会先取word[0]越界。✅ 显式处理word.empty()。7. 递归参数用值传递大对象❌bool dfs(std::vectorstd::vectorchar board, ...)每次递归拷贝整个网格。✅ 用const传递只读的网格visited用引用传递。8. 认为复杂度是 O(m·n·L)❌ 把每个格子的四方向搜索当成线性。✅ 分支因子是常数 4上界是 O(m·n·4^L)实际靠剪枝远小于这个数。总结要点结论搜索方式二维网格 DFS 回溯状态当前位置(i, j)和已匹配长度k去重路径级visited进入置位、离开复位方向上下左右四个不能走对角线时间上界O(m·n·4^L)空间O(m·n L)关键顺序先判越界再访问board[i][j]词语搜索的代码骨架很小正确性几乎全在细节里边界检查的顺序、visited的恢复、空网格和空单词的处理。把「进入分支前改状态、离开分支时还原」这个模式写熟回溯类题目就有了共同的模板。