中国建设银行悦生活网站,食品公司网站设计项目,专业机械设计公司,德州网站建设优化摘要
剑指 Offer 12. 矩阵中的路径
一、回溯算法解析
本问题是典型的矩阵搜索问题#xff0c;可使用 深度优先搜索#xff08;DFS#xff09; 剪枝解决。
深度优先搜索#xff1a; 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归#xff0c;先朝一个方向搜…摘要
剑指 Offer 12. 矩阵中的路径
一、回溯算法解析
本问题是典型的矩阵搜索问题可使用 深度优先搜索DFS 剪枝解决。
深度优先搜索 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归先朝一个方向搜到底再回溯至上个节点沿另一个方向搜索以此类推。剪枝 在搜索中遇到 这条路不可能和目标字符串匹配成功 的情况例如此矩阵元素和目标字符不同、此元素已被访问则应立即返回称之为 可行性剪枝 。DFS 解析
递归参数当前元素在矩阵 board 中的行列索引i和j 当前目标字符在word中的索引k。
终止条件
返回false (1) 行或列索引越界或(2) 当前矩阵元素与目标字符不同或(3) 当前矩阵元素已访问过 (3) 可合并至 (2) 。返回 truek 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[k1..]则返回 true否则返回 false* 这样我们对每一个位置 (i,j)都调用函数 check(i,j,0) 进行检查只要有一处返回 true就说明网格中能够找到相应的单词否则说明不能找到。* Date 2022/12/6 9:54* Created by xjl*/
public class JZ12矩阵中的路径 {int[][] dictnew 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 flagcheck(board,visited,newi,newj,word,k1);if (flag){resulttrue;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[][] dirctnew int[][]{{1,0},{-1,0},{0,1},{0,-1}};public boolean exist3(char[][] board, String word) {int hboard.length;int wboard[0].length;boolean[][] visitnew boolean[h][w];for (int i0;ih;i){for (int j0;jw;j){boolean resultcheck3(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 (kword.length()-1){return true;}visit[i][j]true;boolean resultfalse;for (int[] dir:dirct){int newiidir[0];int newjjdir[1];if (newi0newiboard.lengthnewj0newjboard[0].length){if (!visit[newi][newj]){boolean rescheck(board,visit,newi,newj,word,k1);if (res){resulttrue;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)因为函数返回后系统调用的栈空间会释放。最坏情况下 KMN递归深度为MN 此时系统栈使用 O(MN)的额外空间。
博文参考
《leetcode》
