《剑指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) {// 点上的字母等于目标字符串的第一个字母时，进行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*3^L) ：外层遍历矩阵为NM，dfs一次最多为3^L。

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