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

发布时间:2023年12月24日

剑指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*3L) :外层遍历矩阵为NM,dfs一次最多为3L

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

文章来源:https://blog.csdn.net/m0_56199449/article/details/135130771
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。