剑指offer 12.矩阵中的路径 Python解法

题目描述:

判断一个矩阵中是否存在一条包含某字符串的所有字符的路径。但是经过了某一个格子,就不能再回去了。

 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例: board = [ [‘A’,’B’,’C’,’E’], [‘S’,’F’,’C’,’S’], [‘A’,’D’,’E’,’E’] ] 给定 word = “ABCCED”, 返回 true. 给定 word = “SEE”, 返回 true. 给定 word = “ABCB”, 返回 false.

分析:

写在前面,这题超级绕人。

要求用过的字母不能再使用,所以用*替换找到的字母。

扰人的地方在哪呢?递归。怎么写递归函数,我的一点点经验是:

1、首先就把递归函数的功能定好。调用递归函数时候,仅仅把他当成实现所定义的功能的普通功能函数使用。递归函数还要前后对应,不去管他的递归,假设调用的递归函数已经执行完了,那么后边的代码实现的功能要和开头对应上。(一会看具体例子中*赋值和还原的两行代码对应上)

2、递归函数总要有结束条件,基本是写在最开始的。

3、虽然很不容易理解,这也是递归难的原因。

# 回溯法.这题超级绕人
# 详细参考:https://darktiantian.github.io/%E7%9F%A9%E9%98%B5%E4%B8%AD%E5%8D%95%E8%AF%8D%E7%9A%84%E8%B7%AF%E5%BE%84%EF%BC%8C%E5%BE%88%E5%A4%9A%E4%BA%BA%E9%83%BD%E9%94%99%E4%BA%86/
# 参考链接里有一个很巧妙地测试用例。
class Solution:
    def exist(self, board, word):
        l1 = len(board)             # 行数
        l2 = len(board[0])          # 列数
        
        def spread(i,j,w):          # 函数功能:判断当前位置之后的字母是否都能找到
            if not w :              # 当字符串是空时候,返回True。”因为如果能找到,最后肯定是空“
                return True
            initial ,board[i][j] = board[i][j],'*'      # 将用过的字母用*抹去,并用临时变量存储他
            flag = False                                # 标志位,置为false
            #print('({}, {}) {}, {}'.format(i, j, w, board))
            for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):       # 循环查找上下左右四个位置
                if 0<=x<l1 and 0<=y<l2 and board[x][y] == w[0]: # 如果当前查找的是合法且匹配的
                    if spread(x,y,w[1:]):                       # 递归调用
                        flag = True                   # 递归结束之后,标志位置为true,表示ok
                        break                         # 结束for循环
            board[i][j] = initial                     # for循环结束后,一步一步的还原二位列表中的*
            #print('flag{}, recover ({}, {}), after {}'.format(flag, i, j, board))
            return flag

        for i in range(l1):               # 遍历每个元素,找符合条件的第一个字母
            for j in range(l2):
                if board[i][j] == word[0] and spread(i,j,word[1:]):
                    return True
        return False
# 回溯在那呢?
# 答:17行 if spread(x,y,w[1:]):   # 递归调用
# 如果spread返回的是False,就执行20行:board[i][j] = initial   即为回溯。
# 比如说,for循环在判断’下‘位置时候,执行17行的spread,这个spread返回的是False
#(即下一步的上下左右都执行完了,然后返回22行的false),
#接着就把上一步的*置换回去;
# 注意,此时刚刚的for循环还没执行完呢!接着执行’左‘位置,执行17行的spread。。。。(最绕人的就是在这)

 

    原文作者:国宝小十三
    原文地址: https://blog.csdn.net/dududududou/article/details/93111593
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞