【leetcode】剑指 Offer 12. 矩阵中的路径
2022/1/1 23:38:12
本文主要是介绍【leetcode】剑指 Offer 12. 矩阵中的路径,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
剑指 Offer 12. 矩阵中的路径
分析
其实就是个深度优先搜索。可以设置一个visit数组,标记已经走过的路段。注意判断dfs的退出条件。
写递归就是这样,先想好退出条件,再不断的缩小问题规模,就这样。
深度优先搜索法
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: if len(board) == 0 or len(board[0]) == 0: return word == '' x,y = len(board), len(board[0]) visited = [[False for i in range(y)] for j in range(x)] for i in range(len(board)): for j in range(len(board[0])): if self.dfs(visited, i, j, board, word): return True return False def dfs(self, visited, x, y, board, word): if not word: return True target = word[0] if target != board[x][y]: return False if not word[1:]: return True visited[x][y] = True if x-1>=0 and not visited[x-1][y]: flag = self.dfs(visited, x-1, y, board, word[1:]) if flag: return flag if x+1 < len(board) and not visited[x+1][y]: flag = self.dfs(visited, x+1, y, board, word[1:]) if flag: return flag if y-1>=0 and not visited[x][y-1]: flag = self.dfs(visited, x, y-1, board, word[1:]) if flag: return flag if y+1<len(board[0]) and not visited[x][y+1]: flag = self.dfs(visited, x, y+1, board, word[1:]) if flag: return flag visited[x][y] = False return False
这篇关于【leetcode】剑指 Offer 12. 矩阵中的路径的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-20whatsapp webhook 回调的签名验证偶尔会失败是什么原因-icode9专业技术文章分享
- 2024-09-19Excel数据导出课程:初学者必备教程
- 2024-09-19Excel数据导入课程:新手入门指南
- 2024-09-19RBAC的权限管理入门教程
- 2024-09-19如何使用Svg Sprite Icon制作图标
- 2024-09-19uniapp 如何实现点赞后全局更新数据-icode9专业技术文章分享
- 2024-09-19云函数怎么运行wx-server-sdk-icode9专业技术文章分享
- 2024-09-19"dependencies": { "wx-server-sdk": "latest" },是什么意思-icode9专业技术文章分享
- 2024-09-16优化批处理流程:自定义BatchProcessorUtils的设计与应用
- 2024-09-15laravel collect游标批量插入的方法示例-icode9专业技术文章分享