79. 单词搜索

难度：🟡 Medium | 标签：回溯、矩阵 | 状态：⬜ LeetCode 链接

思路

从每个格子起 DFS。访问时临时标记（如改成 #），回溯时复原。

代码

class Solution {
    int R, C;
    bool dfs(vector<vector<char>>& g, const string& w, int i, int j, int k) {
        if (k == (int)w.size()) return true;
        if (i < 0 || j < 0 || i >= R || j >= C || g[i][j] != w[k]) return false;
        char saved = g[i][j];
        g[i][j] = '#';
        bool ok = dfs(g, w, i + 1, j, k + 1) || dfs(g, w, i - 1, j, k + 1)
               || dfs(g, w, i, j + 1, k + 1) || dfs(g, w, i, j - 1, k + 1);
        g[i][j] = saved;
        return ok;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        R = board.size(); C = board[0].size();
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < C; ++j)
                if (dfs(board, word, i, j, 0)) return true;
        return false;
    }
};

复杂度

• 时间 O(R · C · 4^L)，L 是 word 长度
• 空间 O(L) 递归栈

易错 / 回顾

• 必须回溯复原（与 200 题岛屿染色不同！）
• 用 # 标记访问，避免重复经过同一格
• 也可用 visited 矩阵，但污染矩阵法更省空间