温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

剑指offer:矩阵中的路径

发布时间:2020-03-31 05:06:49 来源:网络 阅读:205 作者:Jayce_SYSU 栏目:编程语言

题目描述
请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

class Solution:
    """
    判断迷宫/棋盘内是否有解的一个方法是回溯法。

    当位于坐标(i, j)的时候,如果当前位置有效,则往所有可能的方向都走一步,否则回退到上一步

    回溯一般可以基于递归或栈来实现。
    以递归为例,若当前位置合法(未被剪枝去掉),则从当前位置出发,继续探索可能的位置,否则回退到
    上一个位置
    """
    def hasPath(self, matrix, path):
        def helper(path_, row, col):
            """
            由(row, col)出发,探索所有可能的位置(递),
            当发现有解或需要剪枝的时候就返回上一步(归)
            :param path_: 剩余待查找的路径
            :param row: 当前所在的行
            :param col:当前所在的列
            :return: 是否有解
            """
            if not path_:
                return True
            if (row >= rows or row < 0 or col >= cols or col < 0
                    or matrix[row][col] != path_[0]):
                return False

            temp = matrix[row][col]  # 记录当前位置的值,以便回溯的时候还原
            matrix[row][col] = '#'  # 标记为已走过
            # 探索左右可能的位置(子节点)
            res = (helper(path_[1:], row, col + 1)
                   or helper(path_[1:], row, col - 1)
                   or helper(path_[1:], row + 1, col)
                   or helper(path_[1:], row - 1, col))
            matrix[row][col] = temp  # 回溯时还原前面的标记,因为回溯后这个点相当于没走过
            return res

        if not path:
            return True
        if not matrix:
            return False
        rows, cols = len(matrix), len(matrix[0])

        for i in range(rows):
            for j in range(cols):
                # 这里可以先判断是否符合起点再进行递归也可以直接递归,但是先判断可以减少开销
                if matrix[i][j] == path[0]:
                    if helper(path, i, j):
                        return True

        return False
向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI