跳到主要内容

LeetCode 79. 单词搜索

本节目标

在网格中回溯选择四个方向，并在每条路径结束后恢复格子。

这道题是约束型回溯通向网格搜索的桥梁：当前格既要匹配单词字符，又只能在本条路径中使用一次；搜索结束后必须恢复它，交给其他起点和分支继续使用。

查看 LeetCode 原题

题意与约束​

给定字符网格和单词，判断是否存在一条由上下左右相邻格组成的路径，使路径字符依次拼成该单词。同一个格子不能在同一条路径中重复使用，但可以被不同候选路径复用。

朴素思路与瓶颈​

从任意格向四个方向盲目扩展，会把字符不匹配、越界和重复使用格子的状态也带入下一层。为每个起点维护永久访问集合同样不对：一次失败路径访问过的格子仍可能属于另一次成功路径。

状态、选择与现场恢复​

定义 dfs(row, column, index)：尝试让网格坐标 (row, column) 匹配 word[index]。越界、字符不等或当前格已被本路径标记时立即失败。若 index 已是最后一个字符，则该路径成功。

匹配但未完成时，先保存原字符并把当前格临时替换为标记，再递归尝试四个方向。无论四个方向中是否找到答案，都在返回前写回原字符。外层枚举每个格子作为首字符起点；因此“标记—递归—恢复”只限制当前路径，不会污染其他搜索。

正确性依据​

每次递归只在当前字符匹配且格子未被当前路径使用时前进，因此任一成功路径的字符顺序正确且没有重复格。四个方向被全部枚举，外层也枚举所有起点，故任一合法路径都会被尝试。临时标记阻止一条路径重复使用格子，而返回前恢复使兄弟分支和其他起点仍能使用该格，恰好符合题目限制。

代码实现​

C++17
#include <string>
#include <vector>

using namespace std;

class Solution {
private:
    bool dfs(vector<vector<char>>& board, const string& word, int row, int column, int index) {
        if (row < 0 || row >= static_cast<int>(board.size()) || column < 0 ||
            column >= static_cast<int>(board[0].size()) || board[row][column] != word[index]) {
            return false;
        }
        if (index == static_cast<int>(word.size()) - 1) {
            return true;
        }

        const char original = board[row][column];
        board[row][column] = '#';
        const bool found = dfs(board, word, row - 1, column, index + 1) ||
                           dfs(board, word, row + 1, column, index + 1) ||
                           dfs(board, word, row, column - 1, index + 1) ||
                           dfs(board, word, row, column + 1, index + 1);
        board[row][column] = original;
        return found;
    }

public:
    bool exist(vector<vector<char>>& board, string word) {
        if (word.empty()) {
            return true;
        }
        if (board.empty() || board[0].empty()) {
            return false;
        }

        for (int row = 0; row < static_cast<int>(board.size()); row++) {
            for (int column = 0; column < static_cast<int>(board[row].size()); column++) {
                if (dfs(board, word, row, column, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
};

复杂度分析​

设网格大小为 m × n，单词长度为 L。外层最多尝试 m × n 个起点；每层至多探索四个方向，故最坏搜索时间为 O(mn · 4^L)。递归深度最多 L，原地标记不另建访问数组，额外空间为 O(L)（不计输入棋盘的暂时改写）。

易错点​

  • 允许同一条路径折返到已经走过的格子，导致 ABCB 这类反例被误判为真。
  • 只在失败分支恢复字符，成功路径提前返回时让棋盘残留标记。
  • 把访问状态放在函数外永久保存，错误阻断其他起点。
  • 先访问邻居再检查当前字符，使 index 与棋盘路径错位。

模式迁移​

当网格路径的访问限制只属于当前尝试时，使用回溯式 DFS 与现场恢复；当一个格子一旦访问就不应再被任何路径使用时，才使用永久标记的遍历式 DFS。下一栏的连通块问题会专门区分这两种语义。