• python每日一题【剑指 Offer 12. 矩阵中的路径】


    day22-2022.11.17

    题目信息来源
    作者:Krahets
    链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm
    来源:力扣(LeetCode)

    剑指 Offer 12. 矩阵中的路径

    给定一个 m × n m\times n m×n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。

    单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

    输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
    输出:true
    输入:board = [["a","b"],["c","d"]], word = "abcd"
    输出:false
    
    • 1
    • 2
    • 3
    • 4

    提示:

    • m == board.length
    • n = board[i].length
    • 1 <= m, n <= 6
    • 1 <= word.length <= 15
    • board 和 word 仅由大小写英文字母组成

    知识点

    1. 深度优先搜索DFS

    链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/58d5vh/

    可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归,先朝一个方向搜到底,再回溯至上个节点,沿另一个方向搜索,以此类推。

    • 递归参数
    • 终止条件
    • 递推工作
    • 返回值
    1. 剪枝:将要遍历的先进行判断,不可能的直接去除

    题解

    我的垃圾版本,不会回溯,暂时没想到好的办法,出现错误的测试为 [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]],"SEE",这个刚好就是一个需要回溯的例子。

    class Solution:
        def exist(self, board, word) -> bool:
            # 需要一个列表存储,存储已选择的路径
            # 有可能存在多个选择,存在一个候选列表,如果下一个也满足,再加入已选列表
            # 坐标的变化,要考虑边界
            # 如果找不到,就为False
            choose_list = []        # 已选点集合
            candidate_list = []     # 候选集合
            # 找起点
            result = False
            x, y, k = 0, 0, 0
            for i in range(len(board)):
                for j in range(len(board[0])):
                    # 找起点
                    if board[i][j]==word[0]:
                        x, y = i, j # 初始化起点,从第二个字母开始找
                        choose_list=[[x, y]]
                        for k in range(1, len(word)):
                            find_letter = False
                            # letter候选值的坐标
                            if x-1>=0 and [x-1,y] not in choose_list:candidate_list.append([x-1,y])
                            if x+1<len(board) and [x+1,y] not in choose_list:candidate_list.append([x+1,y])
                            if y-1>=0 and [x,y-1] not in choose_list:candidate_list.append([x,y-1])
                            if y+1<len(board[0]) and [x,y+1] not in choose_list:candidate_list.append([x,y+1])
                            # 遍历候选坐标
                            for m,n in candidate_list:
                                # 如果当前m,n符合要求,则将m,n纳入choose_list,更新x,y为m,n
                                if board[m][n]==word[k]:
                                    choose_list.append([m,n])
                                    x, y = m, n
                                    find_letter = True
                                    # 如果找到了,就不用再找了,继续下一个字母
                                    break
                            candidate_list = []
                            result = find_letter
                            if find_letter==False:
                                break
                            elif find_letter==True and k==len(word)-1:
                                return find_letter
            return result
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    题解:官方

    前一章是动态规划,就想着是不是不用回溯好。但是这个题,似乎还是递归好一点:因为子问题结构相似。我的破方法就不能够回溯,在 (i-1,j), (i+1,j), (i,j-1), (i,j+1) 四种并列可能性中有一个即可。有一条路可以走通即可,但是我这个如果一个路一开始走通,后面走不通,就不能回去寻找未尝试的并列可能性。

    链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm/58d5vh/

    DFS 解析:

    • 递归参数: 当前元素在矩阵 board 中的行列索引 i 和 j ,当前目标字符在 word 中的索引 k 。
    • 终止条件:
      • 返回 false : (1) 行或列索引越界 或 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过 ( (3) 可合并至 (2) ) 。
      • 返回 true: k = len(word) - 1 ,即字符串 word 已全部匹配。
    • 递推工作:
      • 标记当前矩阵元素: 将 b o a r d [ i ] [ j ] board[i][j] board[i][j]修改为 空字符 ‘’ ,代表此元素已访问过,防止之后搜索时重复访问。
      • 搜索下一单元格: 朝当前元素的 上、下、左、右 四个方向开启下层递归,使用 或 连接 (代表只需找到一条可行路径就直接返回,不再做后续 DFS ),并记录结果至 res 。
      • 还原当前矩阵元素: 将 b o a r d [ i ] [ j ] board[i][j] board[i][j]元素还原至初始值,即 $word[k] $。
    • 返回值: 返回布尔量 res ,代表是否搜索到目标字符串。
    class Solution:
        def exist(self, board, word) -> bool:
            def find(i, j, k):
                if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or board[i][j]!=word[k]:return False
                if k==len(word)-1:return True
                board[i][j] = ''
                result = find(i-1,j,k+1) or find(i+1,j,k+1) or find(i,j-1,k+1) or find(i,j+1,k+1)
                board[i][j] = word[k]
                return result
            k = 0
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if find(i,j,k):return True
            return False
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
  • 相关阅读:
    遥感IDL二次开发(大气校正)
    Mybatis-Plus之连表查询
    文盘 Rust -- tokio 绑定 cpu 实践
    【CV】第 9 章:图像分割
    tfts时间序列-sine样本
    jquery中 offset()计算的偏移量 和 原生Dom计算的偏移量不一致;
    让ubuntu bash像git bash一样
    Java ThreadPoolExecutor 线程池
    Linux实操篇-定时任务调度
    c++ uml时序图
  • 原文地址:https://blog.csdn.net/qq_42896431/article/details/127986604