12 矩阵中的路径

剑指 Offer 12. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

解题思路：

可以使用深度优先搜索和剪枝法来做。

深度优先搜索：通过递归，往一个方向一直搜索下去，直到发现路径不符合要求或者单词串已经走完并且全部字符都匹配到了，就返回。如果是前者，则向另一个方向重新递归，否则返回 $true$。
剪枝法：当发现路径中有一个字符不合要求时，就可以提前结束递归。

DFS函数

递归参数：当前元素在矩阵中的位置$（x, y）$，当前目标字符在 word 中的位置 $k$ 。

终止条件：

返回 $false$：$x$ 或 $y$ 越界，或者当前矩阵元素与目标字符不同，或者当前矩阵元素已经遍历过。（三种情况）
返回 $true$： $k = len(word) - 1$，即字符串已经全部匹配完。

递推工作：

记录当前矩阵元素 $c$ 并将对应位置 $(x, y)$ 置为 '\0'，表示此元素已经访问过，防止之后重新重复访问。
搜索下一个单元格：朝当前元素的上、下、左、右方向进行递归，使用或连接递归结果，如果某个方向符合要求，则不用继续递归。
还原当前元素：将 $(x,y)$ 位置还原为 $c$ 。

代码：

public boolean exist(char[][] board, String word) {
    if (board == null || board.length == 0) {
        return false;
    }
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            // 不用每个矩阵元素都进行递归，当发现与 word 第一个元素相同时再进行递归
            if (board[i][j] == word.charAt(0)
                    && hasPath(board, i, j, word, 0)) {
                return true;
            }
        }
    }
    return false;
}

private boolean hasPath(char[][] board, int x, int y,
                        String word, int idx) {
    if (word.length() == idx) {
        return true;
    }
    if (y < 0 || x < 0
            || x >= board.length || y >= board[0].length
            || board[x][y] != word.charAt(idx)) {
        return false;
    }
    // 置为 '\0' 字符，等遍历完一个位置之后，在设置回原来的字符，可以免去设置一个遍历的 visited 表
    board[x][y] = '\0';
    boolean hasPath = hasPath(board, x + 1, y, word, idx + 1)
            || hasPath(board, x - 1, y, word, idx + 1)
            || hasPath(board, x, y + 1, word, idx + 1)
            || hasPath(board, x, y - 1, word, idx + 1);
    // 由上面的代码可知 board[x][y] = word.charAt(idx)
    board[x][y] = word.charAt(idx);
    return hasPath;
}

复杂度分析

时间复杂度$O(3^KMN)$ ：最差情况下，需要遍历矩阵中长度为 K 的所有方案，时间复杂度为 $O(3^K)$；举证共有 $MN$ 个起点，所以时间复杂度 $O(MN)$ 。
- 方案数计算：遍历过程有上、下、左、右四个方向可以进行递归，舍弃上层递归的方向，还剩下三个方向可以递归，剩下 $3$ 种选择，因此方案书的复杂度为 $O(3^K)$。
空间复杂度$O(K)$：搜索过程的递归深度不超过 $K$ ，因此需要总共需要的占空间为 $O(K)$。因为系统调用后，函数栈的空间会被释放。最差情况是 $K = MN$，那么此时需要占空间 $O(MN)$ 。

目录CONTENT

12 矩阵中的路径

评论区