栏目手机版 企业网站,wordpress 首页链接,wordpress360插件,完成公司门户网站建设剑指offer原题:矩阵中的路径 请设计一个函数#xff0c;用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始#xff0c;每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格#xff0c;那么该路径不能再… 剑指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) {// 点上的字母等于目标字符串的第一个字母时进行dfsif(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) 外层遍历矩阵为NMdfs一次最多为3L。
空间复杂度O(NM)主要借助了辅助空间vis大小NM。
