《剑指offer》Java版--12.矩阵中的路径（DFS+剪枝）

剑指offer原题:矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfee”的路径(路径中的字母用下画线标出)。但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

LeetCode原题：https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/description/

思路：DFS+剪枝

class Solution {
    int[][] pos = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    char[][] grid;
    String target;
    boolean[][] vis;
    int m, n;
    private void init(char[][] grid, String target) {
        this.grid = grid;
        this.target = target;
        this.m = grid.length;
        this.n = grid[0].length;
        this.vis = new boolean[m][n];
    }

    public boolean wordPuzzle(char[][] grid, String target) {
        if(grid.length == 0 || Objects.isNull(target)) return false;
        init(grid, target);
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                // 点上的字母等于目标字符串的第一个字母时，进行dfs
                if(target.charAt(0) == grid[i][j]) {
                    if(dfs(i, j, 0)) return true;
                }
            }
        }
        return false;
    }
    // x,y 代表当前访问的点，index 代表目标字符串的下标
    public boolean dfs(int x, int y, int index) {
        // 索引来到了目标串的最后说明找到了
        if(index == target.length() - 1) return true;
        vis[x][y] = true;
        for(int i = 0; i < 4; ++i) {
            int nextX = x + pos[i][0];
            int nextY = y + pos[i][1];
            // 判断是否越过边界值；判断接下来的点是否已访问；判断接下来访问的点上的字母是否符合预期；
            if(isValid(nextX, nextY) && !vis[nextX][nextY]
                    && target.charAt(index + 1) == grid[nextX][nextY]) {
                if(dfs(nextX, nextY, index + 1)) return true;
            }
        }
        vis[x][y] = false;
        return false;
    }

    private boolean isValid(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

NM代表矩阵的长宽，L目标字符串长度。

时间复杂度O(NM*3^L) ：外层遍历矩阵为NM，dfs一次最多为3^L。

空间复杂度O(NM)：主要借助了辅助空间vis大小NM。