力扣 - 剑指 Offer 12. 矩阵中的路径
2021/11/21 6:09:55
本文主要是介绍力扣 - 剑指 Offer 12. 矩阵中的路径,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
剑指 Offer 12. 矩阵中的路径
思路1(回溯、DFS)
- 这题可以使用回溯+递归来解决,思路如下:
- 将二维数组的每一个元素都作为起点进行回溯查找
- 每次查找的时候,都有四个方向,但是上一个方向不能再次被遍历,因此需要将遍历过的位置进行做标记,递归返回的时候再还原
- 递归过程中要判断一些条件:越界直接返回false、当前字符和
word
中的不匹配也直接返回false - 何时为匹配成功呢?只要能匹配到
word
的最后一个字符,即curIndex == cs.length-1
(curIndex为每次搜索的深度,不过是从0开始的,就是在word
中的位置;cs.length-1
为最后一个字符的索引位置),因此后面剩下的就不用查找了
代码
class Solution { public boolean exist(char[][] board, String word) { char[] cs = word.toCharArray(); // 遍历整个二维数组,即将每个字符作为第一个字符进行尝试 for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { // 只要有一条符合条件,则返回true if (dfs(board, cs, i, j, 0)) { return true; } } } // 没找到 return false; } public boolean dfs(char[][] board, char[] cs, int i, int j, int curIndex) { // 超过二维数组边界就返回false // 字符不匹配也直接结束递归 if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != cs[curIndex]) { return false; } // 如果以及全部匹配到了,就直接返回true,而不用继续匹配剩下的啦 if (curIndex == cs.length - 1) { return true; } // 能递归到这里,说明当前cs中curIndex索引对应的字符和boards是匹配的 // 因此我们需要吧遍历过的字符设置为空白,防止再次遍历 board[i][j] = '\0'; boolean res = dfs(board, cs, i + 1, j, curIndex + 1) || dfs(board, cs, i - 1, j, curIndex + 1) || dfs(board, cs, i, j + 1, curIndex + 1) || dfs(board, cs, i, j - 1, curIndex + 1); // 回溯的时候要把原来设置为空白字符的还原 board[i][j] = cs[curIndex]; // 只要出现true,就一路返回 return res; } }
复杂度分析
- 时间复杂度:\(O(MN·3^K)\),二维数组共有M·N个起点;然后对于每个起点来说,每步都有三个方向可以选择(不包括上一个方向),最长要走的步数就是
word
的长度K
,因此复杂度为\(3^K\) - 空间复杂度:\(O(K)\),递归深度最深也就是
word
的长度
这篇关于力扣 - 剑指 Offer 12. 矩阵中的路径的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20接口模块封装入门教程
- 2024-09-20请求动作封装入门教程
- 2024-09-20登录鉴权学习:新手入门教程
- 2024-09-20后台管理开发学习:新手入门指南
- 2024-09-20后台管理系统开发学习:从入门到实践
- 2024-09-20后台开发学习:从入门到初级实战指南
- 2024-09-20后台综合解决方案学习:从入门到实践
- 2024-09-20接口模块封装学习入门指南
- 2024-09-20请求动作封装学习:新手入门教程
- 2024-09-20登录鉴权入门:打造安全的用户认证系统