题目描述

给定一个 $m x n$ 二维字符网格 $board$ 和一个字符串单词 $word$ 。如果 $word$ 存在于网格中，返回 $true$ ；否则，返回 $false$ 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

提示：

• $1 <= board.length <= 200$
• $1 <= board[i].length <= 200$
• $board$ 和 $word$ 仅由大小写英文字母组成

注意： 本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/

---

算法

(DFS,回溯) $O(nm*3^k)$

从图中每个点作为起点开始搜索长度为 $word.size()$ 的序列，如果匹配成功则返回 $true$，否则从下一个点开始搜索，直到所有点作为起点都没有匹配成功，则返回 $false$。

搜索的逻辑：

1. 递归函数的含义：bool dfs(int x, int y, int u, string word)，$(x, y)$ 表示当前正在搜索的坐标，$u$ 表示当前正在匹配 $word$ 中的哪个字母。
2. 递归的出口条件：如果当前坐标上的值和 $word$ 的第 $u$ 个字母不匹配则返回 $false$，如果当前匹配完了 $word$ 的最后一个字母，则返回 $true$。
3. 单层递归的逻辑：如果当前字母匹配成功，则标记已访问，并开始匹配下一个字母，依次枚举剩下的三个方向，继续递归匹配，如果匹配成功，则返回 $true$，否则三个方向都匹配失败返回 $false$。

时间复杂度

$O(nm3^k)$，$DFS$ 搜索的时间为 $3^k$，$k$ 表示字符串的长度，最坏情况下每个点都要作为起点搜一遍，所以时间复杂度为 $O(nm3^k)$。

空间复杂度

$O(nm)$

C++ 代码

class Solution {
public:
    vector<vector<char>> g;
    vector<vector<bool>> st;
    int n, m;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    bool dfs(int x, int y, int u, string word) {
        if (g[x][y] != word[u]) return false;
        if (u == word.size() - 1) return true;

        st[x][y] = true;
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) continue;
            if (dfs(a, b, u + 1, word)) return true;
        }
        st[x][y] = false;

        return false;
    }

    bool exist(vector<vector<char>>& board, string word) {
        g = board;
        n = g.size(), m = g[0].size();
        st = vector<vector<bool>>(n, vector<bool>(m, false));
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (dfs(i, j, 0, word)) return true;
        return false;
    }
};