栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

剑指offer—JZ12矩阵中的路径(Python解)

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

剑指offer—JZ12矩阵中的路径(Python解)

题目描述

请设计一个函数,用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则该路径不能再进入该格子。 

知识点:递归与回溯

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程,最重要的就是查看能不能讲原本的问题分解为更小的子问题,这是使用递归的关键。

如果是线型递归,子问题直接回到父问题不需要回溯,但是如果是树型递归,父问题有很多分支,我需要从子问题回到父问题,进入另一个子问题。因此回溯是指在递归过程中,从某一分支的子问题回到父问题进入父问题的另一子问题分支,因为有时候进入第一个子问题的时候修改过一些变量,因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。

思路:要在矩阵中找到从某个位置开始,位置不重复的一条路径,路径为某个字符串,那我们肯定是现在矩阵中找到这个位置的起点。没办法直观的找出来,只能遍历矩阵每个位置都当作起点试一试。

找到起点后,它周围的节点是否可以走出剩余字符串子串的路径,该子问题又可以作为一个递归。因此,可以用递归来解决。

  • 终止条件: 到了矩阵的边界或者是下一个字符与这个位置的字符不匹配,或者字符串匹配完成,都需要返回,
  • 返回值: 将每条查询路径是否有这样的字符串返回,即true or false。
  • 本级任务: 检查这个位置的字符与字符串中这个字符是否匹配,并向与它相邻的四个方向(且不是来的方向)延伸子问题。

class Solution:
    def dfs(self, matrix: List[List[str]], n: int, m: int, i: int, j: int, word: str, k: int, flag: List[List[bool]]) -> bool:
        if i < 0 or i >= n or j < 0 or j >= m or (matrix[i][j] != word[k]) or flag[i][j]:
            #下标越界、字符不匹配、已经遍历过不能重复
            return False
        #k为记录当前第几个字符
        if k == len(word) - 1:
            return True
        flag[i][j] = True
        #该结点任意方向可行就可
        if (self.dfs(matrix, n, m, i - 1, j, word, k + 1, flag) 
            or self.dfs(matrix, n, m, i + 1, j, word, k + 1, flag) 
            or self.dfs(matrix, n, m, i, j - 1, word, k + 1, flag) 
            or self.dfs(matrix, n, m, i , j + 1, word, k + 1, flag)):
            return True 
        #没找到经过此格的,此格未被占用
        flag[i][j] = False 
        return False

    def hasPath(self , matrix: List[List[str]], word: str) -> bool:
        if len(matrix) == 0:
            return False
        n = len(matrix)
        m = len(matrix[0])
        #初始化flag矩阵记录是否走过
        flag = [[False for i in range (m)] for j in range(n)]
        #遍历矩阵找起点
        for i in range(n):
            for j in range(m):
                #通过dfs找到路径
                if self.dfs(matrix, n, m, i, j, word, 0, flag):
                    return True
        return False

复杂度分析:

  • 时间复杂度:O(mn∗k3)O(mn*k^3)O(mn∗k3),其中mmm与nnn为矩阵的边长,kkk为字符串的长度,遍历一次矩阵,每次条递归最坏遍历深度为kkk,看起来是四个方向,但是有一个方向是来的方向不重复访问,所以是三叉树型递归,因此递归复杂度为O(k3)O(k^3)O(k3)
  • 空间复杂度:O(mn)O(mn)O(mn),辅助二维数组记录是否走过某节点使用了空间
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/918322.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号