79. 单词搜索

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

回溯

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];  // 记录访问状态

        // 遍历每个单元格作为起始点
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (dfs(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, boolean[][] visited, int row, int col, int index) {
        // 以下是对当前层的操作
        // 失败条件
        if (board[row][col] != word.charAt(index)) {
            return false;
        }
        // 重点。成功条件。
        if (index == word.length() - 1) {
            return true;
        }
        visited[row][col] = true;
        
        // 进入下一层
        // 定义四个方向：右、下、左、上
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // 遍历四个方向
        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];

            // 检查新位置是否在边界内且未被当前路径访问
            if (isValid(board, visited, newRow, newCol)) {
                if (dfs(board, word, visited, newRow, newCol, index + 1)) {
                    return true;  // 立即返回 true
                }
            }
        }
        
        // 取消当前单元格的访问标记（回溯）。为什么需要回溯？因为本路径上不允许重复访问，
        // 但是其它路径可以重复访问这个节点，这和岛屿问题不一样，岛屿问题是只要访问一次就够了，本问题严格来说是组合问题。
        // 重点。
        visited[row][col] = false;

        return false;
    }

    private boolean isValid(char[][] board, boolean[][] visited, int row, int col) {
        return row >= 0 && row < board.length && col >= 0 && col < board[0].length && !visited[row][col];
    }
}

• 时间复杂度：一个非常宽松的上界为 $O\left(M N \cdot 3^L\right)$，其中 $M, N$ 为网格的长度与宽度， $L$ 为字符串 word 的长度。在每次调用函数 dfs 时，除了第一次可以进入 4 个分支以外， 其余时间我们最多会进入 3 个分支 (因为每个位置只能使用一次，所以走过来的分支没法走回去)。由于单词长为 $L$， 故 $\operatorname{dfs}(i, j, 0)$ 的时间复杂度为 $O\left(3^L\right)$， 而我们要执行 $O(M N)$ 次检查。然而，由于剪枝的存在，我们在遇到不匹配或已访问的字符时会提前退出，终止递归流程。 因此，实际的时间复杂度会远远小于 $O\left(M N \cdot 3^L\right)$ 。

  $3^L$可以这样理解：每层递归有3个子递归，递归层数最大是L。

• 空间复杂度: $O(M N)$ 。我们额外开辟了 $O(M N)$ 的 visited 数组，同时栈的深度最大为 $O(\min (L, M N))$ 。 栈的深度可以这样理解：index最多到L返回，边界索引最多到MN返回。