剑指 Offer 12. 矩阵中的路径

摘要

剑指 Offer 12. 矩阵中的路径

一、回溯算法解析

本问题是典型的矩阵搜索问题，可使用 深度优先搜索（DFS）+ 剪枝解决。

• 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
• 剪枝： 在搜索中，遇到 这条路不可能和目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。

DFS 解析：

递归参数：当前元素在矩阵 board 中的行列索引i和j ，当前目标字符在word中的索引k。

终止条件：

• 返回false ：(1) 行或列索引越界或(2) 当前矩阵元素与目标字符不同或(3) 当前矩阵元素已访问过 （(3) 可合并至 (2) ） 。
• 返回 true：k = len(word) - 1 ，即字符串 word 已全部匹配。

递推工作：

• 标记当前矩阵元素： 将 board[i][j] 修改为 空字符 '' ，代表此元素已访问过，防止之后搜索时重复访问。
• 搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
• 还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k] 。

返回值： 返回布尔量 res ，代表是否搜索到目标字符串。

package matrix;/*** @Classname JZ12矩阵中的路径* @Description* 设函数 check(i,j,k) 表示判断以网格的 (i,j) 位置出发，能否搜索到单词 word[k..]，其中 word[k..]* 表示字符串 word从第 k 个字符开始的后缀子串。如果能搜索到，则返回 true，反之返回 false。** 函数 check(i,j,k) 的执行步骤如下：*   如果 board[i][j]≠s[k],当前字符不匹配，直接返回 false。*   如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 true。*   否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 word[k+1..]，则返回 true，否则返回 false* 这样，我们对每一个位置 (i,j)都调用函数 check(i,j,0) 进行检查：只要有一处返回 true，就说明网格中能够找到相应的单词，否则说明不能找到。* @Date 2022/12/6 9:54* @Created by xjl*/
public class JZ12矩阵中的路径 {int[][] dict=new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};/*** @description 使用回溯算法来实现* @param: board* @param: word* @date: 2022/12/6 10:12* @return: boolean* @author: xjl*/public boolean exist(char[][] board, String word) {int h = board.length, w = board[0].length;// 判断时候访问的标志boolean[][] visited = new boolean[h][w];// 逐个遍历来实现for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {// 数组传递  访问标志位  当前的i j的位置  目标word  当前的匹配的字符数boolean flag = check(board, visited, i, j, word, 0);if (flag) {return true;}}}return false;}/*** @description* @param: board 查找的数组* @param: visited 是否已经访问了的数据* @param: i 当前的位置坐标* @param: j 当前的位置坐标* @param: word 目标单词* @param: k 当前匹配的字符数* @date: 2022/12/6 10:15* @return: boolean* @author: xjl*/private boolean check(char[][] board, boolean[][] visited, int i, int j, String word, int k) {// 如果 board[i][j]≠s[k],当前字符不匹配，直接返回 false。if (board[i][j] != word.charAt(k)) {return false;} else if (k == word.length() - 1) {// 表示匹配完成了 就返回truereturn true;}// 访问当前元素visited[i][j] = true;// 设置当前访问的结果 通过判断下一次的结果来 判断是否全部匹配成功了。boolean result = false;for (int[] dir : dict) {int newi = i + dir[0],newj = j + dir[1];// 保证需要在矩阵的内部if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {// 表示没有访问过if (!visited[newi][newj]){boolean flag=check(board,visited,newi,newj,word,k+1);if (flag){result=true;break;}}}}// 设置回来,表示的没有访问过。visited[i][j]=false;return result;}public boolean exist2(char[][] board, String word) {//对应的字符创数组char[] words = word.toCharArray();//开始重第一个开始遍历for(int i = 0; i < board.length; i++) {for(int j = 0; j < board[0].length; j++) {if(dfs(board, words, i, j, 0)) {return true;}}}return false;}//k 表示的是字符数组的下标的位置boolean dfs(char[][] board, char[] word, int i, int j, int k) {//i越界 j越界  字符串不等于数组的这个元素if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) {return false;}//当遍历完成了这返回trueif(k == word.length - 1) {return true;}// 当前字符串char tmp = board[i][j];board[i][j] = '/';//表示是矩阵中的下上右左的是否为下一个boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);// 回溯board[i][j] = tmp;//返回这个数据return res;}int[][] dirct=new int[][]{{1,0},{-1,0},{0,1},{0,-1}};public boolean exist3(char[][] board, String word) {int h=board.length;int w=board[0].length;boolean[][] visit=new boolean[h][w];for (int i=0;i<h;i++){for (int j=0;j<w;j++){boolean result=check3(board,visit,i,j,word,0);if (result){return true;}}}return false;}private boolean check3(char[][] board, boolean[][] visit, int i, int j, String word, int k) {if (board[i][j]!=word.charAt(k)){return false;}if (k==word.length()-1){return true;}visit[i][j]=true;boolean result=false;for (int[] dir:dirct){int newi=i+dir[0];int newj=j+dir[1];if (newi>=0&&newi<board.length&&newj>=0&&newj<board[0].length){if (!visit[newi][newj]){boolean res=check(board,visit,newi,newj,word,k+1);if (res){result=true;break;}}}}visit[i][j]=false;return result;}}

复杂度分析：

M,N 分别为矩阵行列大小， K为字符串word长度。

• 时间复杂度 O((3^K)MN) ： 最差情况下，需要遍历矩阵中长度为K字符串的所有方案，时间复杂度为 O(3K)；矩阵中共有MN个起点，时间复杂度为O(MN) 。
• 空间复杂度 O(K)： 搜索过程中的递归深度不超过K ，因此系统因函数调用累计使用的栈空间占用 O(K)（因为函数返回后，系统调用的栈空间会释放）。最坏情况下 K=MN，递归深度为MN ，此时系统栈使用 O(MN)的额外空间。

博文参考

《leetcode》