矩阵中的路径( DFS 剪枝 回溯)

图片文字说明

解题思路:
本问题是典型的矩阵搜索问题,可使用 深度优先搜索(DFS)+ 剪枝 解决。

深度优先搜索: 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS 通过递归,先朝一个方向搜到底,再回溯至上个节点,沿另一个方向搜索,以此类推。
剪枝: 在搜索中,遇到 这条路不可能和目标字符串匹配成功 的情况(例如:此矩阵元素和目标字符不同、此元素已被访问),则应立即返回,称之为 可行性剪枝


图片文字说明

  1. 理清整体算法架构,构建dfs函数+递归
  2. 确定使用回溯法的话就是,在最一轮一轮的嵌套函数中的最深处满足条件则返回True
  3. 停止条件:
    - 行数 < 0
    - 列数 < 0
    - 行数超过矩阵
    - 列数超过矩阵
    - board【i】【j】 不等于 word【index】
  4. 满足条件
    - index的数量 == word的长度
  5. 标记走过的路,将匹配的board[i][j] 标记为‘’


代码如下:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 回溯法就是嵌套函数,一层层返回
        def dfs(i,j,index):
            # 停止条件有 4个:
            # 1、i < 0 ; 
            # 2、j <0 ; 
            # 3、i 超过行数
            # 4、j 超过列数,
            # 5、且遍历到的board[i][j] != word[index]
            if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or board[i][j] != word[index]:
                return False #传False回溯
            if index == len(word)-1:
                return True  #直到发现index的当前值满足了word长度,则一层一层返回True
            board[i][j] = '' #如果不把走过的路径标记为‘’ ,它会来回匹配
            ##向下 # 向右  #向左  #向上  
            res =  dfs(i+1 , j, index +1) \
                or dfs(i,  j+1 , index+1) \
                or dfs(i-1 ,j , index+1) \
                or dfs(i, j-1, index+1 ) 
            board[i][j] = word[index] # 赋值比对
            return res
            
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i,j,0):
                    return True
        return False

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/


欢迎技术探讨