题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。To do it!
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 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
提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

题解

DFS 回溯法 + 剪枝

以 深度优先搜索 (DFS) 进行矩阵搜索，回溯遍历所有的解空间，当某个字符不匹配或已访问时即可进行 剪枝优化 。

class Solution {
    using vvchar = vector<vector<char>>;
    using vvbool = vector<vector<bool>>;
    bool dfs(vvchar& board, vvbool& visit, int m, int n, int i, int j, string& word, int k) {
        if (k >= word.size()) return true;      // 完成搜索
        if (i < 0 || i >= m || j < 0 || j >= n || visit[i][j] || board[i][j] != word[k])
            return false;                       // 结束或剪枝
        visit[i][j] = true;
        bool ret = 
            dfs(board, visit, m, n, i - 1, j, word, k + 1) || 
            dfs(board, visit, m, n, i + 1, j, word, k + 1) || 
            dfs(board, visit, m, n, i, j - 1, word, k + 1) || 
            dfs(board, visit, m, n, i, j + 1, word, k + 1);
        // 如果这条路行不通，将 visit 改回 false，回溯回去换条路试试
        if (ret == false) visit[i][j] = false;  
        return ret;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == word[0]) {
                    vvbool visit(m, vector<bool>(n, false));
                    if (dfs(board, visit, m, n, i, j, word, 0)) return true;
                }
            }
        }
        return false;
    }
};

复杂度分析：
M, N 为矩阵的行列大小，L 为字符串 word 长度。

时间复杂度 $O(MN3^L)$ $O (M N 3^{L})$ ：最差情况下，需要遍历矩阵中长度为 L 字符串的所有方案，时间复杂度为 $O(3^L)$ $O (3^{L})$ ；矩阵中共有 MN 个起点，时间复杂度为 O(MN) 。
- 方案数计算： 字符串长度为 L ，搜索中的每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）方向，剩下 3 种选择，因此方案数的时间复杂度为 $O(3^L)$ 。
- 当然，这是一个非常宽松的上界，由于剪枝的存在，在遇到不匹配或已访问的字符时会提前退出，终止递归。因此，实际的时间复杂度会远远小于 $O(MN3^L)$ 。
空间复杂度 $O(L)$ ：搜索过程中递归深度不超过 L ，因此系统因函数调用累计使用的栈空间占用 O(L) （函数调用返回后，系统调用的栈空间会释放）。最坏的情况下 K = MN ，即搜索单词和矩阵大小相同，递归深度为 MN ，此时系统栈使用 O(MN) 的额外空间。