题目链接 · 灵神原题解（署名来源）

前置知识

做本题前，你需要有一些网格图 DFS 的经验和回溯的经验。

• 关于网格图 DFS，可以做做 200. 岛屿数量。
• 关于回溯，可以看【基础算法精讲 14】。

基本思路（优化前）

枚举 $i=0,1,2,\dots ,m-1$ 和 $j=0,1,2,\dots ,n-1$，以 $(i,j)$ 为起点开始搜索。

同时，我们还需要知道当前匹配到了 $\mathit{\text{word}}$ 的第几个字母，所以还需要一个参数 $k$。

定义 $\mathit{\text{dfs}}(i,j,k)$ 表示当前在 $\mathit{\text{board}}[i][j]$ 这个格子，要匹配 $\mathit{\text{word}}[k]$，返回在这个状态下最终能否匹配成功（搜索成功）。

分类讨论：

• 如果 $\mathit{\text{board}}[i][j]\ne \mathit{\text{word}}[k]$，匹配失败，返回 $\mathtt{\text{false}}$。
• 否则，如果 $k=\text{len}(\mathit{\text{word}})-1$，匹配成功，返回 $\mathtt{\text{true}}$。
• 否则，枚举 $(i,j)$ 周围的四个相邻格子 $(x,y)$，如果 $(x,y)$ 没有出界，则递归 $\mathit{\text{dfs}}(x,y,k+1)$，如果其返回 $\mathtt{\text{true}}$，则 $\mathit{\text{dfs}}(i,j,k)$ 也返回 $\mathtt{\text{true}}$。
• 如果递归周围的四个相邻格子都没有返回 $\mathtt{\text{true}}$，则最后返回 $\mathtt{\text{false}}$，表示没有搜到。

细节：

• 递归过程中，为了避免重复访问同一个格子，可以用 $\mathit{\text{vis}}$ 数组标记。更简单的做法是，直接修改 $\mathit{\text{board}}[i][j]$，将其置为空（或者 $0$），返回 $\mathtt{\text{false}}$ 前再恢复成原来的值（恢复现场）。注意返回 $\mathtt{\text{true}}$ 的时候就不用恢复现场了，因为已经成功搜到 $\mathit{\text{word}}$ 了。

Python 解法1

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        def dfs(i: int, j: int, k: int) -> bool:
            if board[i][j] != word[k]:  # 匹配失败
                return False
            if k == len(word) - 1:  # 匹配成功！
                return True
            board[i][j] = ''  # 标记访问过
            for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):  # 相邻格子
                if 0 <= x < m and 0 <= y < n and dfs(x, y, k + 1):
                    return True  # 搜到了！
            board[i][j] = word[k]  # 恢复现场
            return False  # 没搜到
        return any(dfs(i, j, 0) for i in range(m) for j in range(n))

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
    static constexpr int DIRS[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> bool {
            if (board[i][j] != word[k]) { // 匹配失败
                return false;
            }
            if (k + 1 == word.length()) { // 匹配成功！
                return true;
            }
            board[i][j] = 0; // 标记访问过
            for (auto& [dx, dy] : DIRS) {
                int x = i + dx, y = j + dy; // 相邻格子
                if (0 <= x && x < m && 0 <= y && y < n && dfs(x, y, k + 1)) { // 没超过边界，并且后续字母都成功匹配
                    return true;
                }
            }
            board[i][j] = word[k]; // 恢复现场
            return false; // 没搜到
        };
        // 每个格子都可以作为起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j, 0)) {
                    return true; // 搜到了！
                }
            }
        }
        return false; // 没搜到
    }
};

第一个优化

比如示例 3，$\mathit{\text{word}}=\mathtt{\text{ABCB}}$，其中字母 $\mathtt{\text{B}}$ 出现了 $2$ 次，但 $\mathit{\text{board}}$ 中只有 $1$ 个字母 $\mathtt{\text{B}}$，所以肯定搜不到 $\mathit{\text{word}}$，直接返回 $\mathtt{\text{false}}$。

一般地，如果 $\mathit{\text{word}}$ 的某个字母的出现次数，比 $\mathit{\text{board}}$ 中的这个字母的出现次数还要多，可以直接返回 $\mathtt{\text{false}}$。

第二个优化

启发：如果 $\mathit{\text{word}}=\mathtt{\text{abcd}}$ 但 $\mathit{\text{board}}$ 中的 $\mathtt{\text{a}}$ 很多，$\mathtt{\text{d}}$ 很少（比如只有一个），那么从 $\mathtt{\text{d}}$ 开始搜索，能更快地找到答案。（即使我们肉眼去找，这种方法也是更快的）

设 $\mathit{\text{word}}$ 的第一个字母在 $\mathit{\text{board}}$ 中出现了 $x$ 次，$\mathit{\text{word}}$ 的最后一个字母在 $\mathit{\text{board}}$ 中出现了 $y$ 次。

如果 $y<x$，我们可以把 $\mathit{\text{word}}$ 反转，相当于从 $\mathit{\text{word}}$ 的最后一个字母开始搜索，这样更容易在一开始就满足 board[i][j] != word[k]，不会往下递归，递归的总次数更少。

加上这两个优化，就可以击败接近 $100\mathrm{\%}$ 了！其中 Java、C++、Go 和 Rust 都可以跑到 0ms。

Python 解法3

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        cnt = Counter(c for row in board for c in row)
        if not cnt >= Counter(word):  # 优化一
            return False
        if cnt[word[-1]] < cnt[word[0]]:  # 优化二
            word = word[::-1]

        m, n = len(board), len(board[0])
        def dfs(i: int, j: int, k: int) -> bool:
            if board[i][j] != word[k]:  # 匹配失败
                return False
            if k == len(word) - 1:  # 匹配成功！
                return True
            board[i][j] = ''  # 标记访问过
            for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):  # 相邻格子
                if 0 <= x < m and 0 <= y < n and dfs(x, y, k + 1):
                    return True  # 搜到了！
            board[i][j] = word[k]  # 恢复现场
            return False  # 没搜到
        return any(dfs(i, j, 0) for i in range(m) for j in range(n))

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
    static constexpr int DIRS[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
    bool exist(vector<vector<char>>& board, string word) {
        unordered_map<char, int> cnt;
        for (auto& row : board) {
            for (char c : row) {
                cnt[c]++;
            }
        }

        // 优化一
        unordered_map<char, int> word_cnt;
        for (char c : word) {
            if (++word_cnt[c] > cnt[c]) {
                return false;
            }
        }

        // 优化二
        if (cnt[word.back()] < cnt[word[0]]) {
            ranges::reverse(word);
        }

        int m = board.size(), n = board[0].size();
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> bool {
            if (board[i][j] != word[k]) { // 匹配失败
                return false;
            }
            if (k + 1 == word.length()) { // 匹配成功！
                return true;
            }
            board[i][j] = 0; // 标记访问过
            for (auto& [dx, dy] : DIRS) {
                int x = i + dx, y = j + dy; // 相邻格子
                if (0 <= x && x < m && 0 <= y && y < n && dfs(x, y, k + 1)) {
                    return true; // 搜到了！
                }
            }
            board[i][j] = word[k]; // 恢复现场
            return false; // 没搜到
        };
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j, 0)) {
                    return true; // 搜到了！
                }
            }
        }
        return false; // 没搜到
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(mn{3}^k)$，其中 $m$ 和 $n$ 分别为 $\mathit{\text{grid}}$ 的行数和列数，$k$ 是 $\mathit{\text{word}}$ 的长度。除了递归入口，其余递归至多有 $3$ 个分支（因为至少有一个方向是之前走过的），所以每次递归（回溯）的时间复杂度为 $\mathcal{O}(3^k)$，一共回溯 $\mathcal{O}(mn)$ 次，所以时间复杂度为 $\mathcal{O}(mn{3}^k)$。
• 空间复杂度：$\mathcal{O}(|\mathrm{\Sigma }|+k)$。其中 $|\mathrm{\Sigma }|=52$ 是字符集合的大小。递归需要 $\mathcal{O}(k)$ 的栈空间。部分语言用的数组代替哈希表，可以视作 $|\mathrm{\Sigma }|=128$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府