跳到主要内容

面试题12. 矩阵中的路径

题目描述​

做题链接：面试题12. 矩阵中的路径

从数组中

[["a","b","c","e"], ["s","f","c","s"], ["a","d","e","e"]]

找 bfcs

解题思路​

经典搜索算法，本题使用深搜DFS比较合适

注意事项

  • 终止条件 if not word: return True 不能漏掉

  • 访问过的节点矩阵：两种实现方法 邻接矩阵表示法、稀疏矩阵标识方式

    1. 邻接矩阵表示法

      flags = [[0]*ncol for _ in range(nrow)]

    2. 稀疏矩阵标识方式

      flags = [(1, 2), (3,4)]

  • 一定要注意结束后 回溯状态

代码​

写法一

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, word):
            if not word: return True # 已经找到
            if not (0 <= i <= len(board) - 1 and \
               0 <= j <= len(board[0]) - 1 and \
               board[i][j] == word[0]): return False
            flag.append((i, j)) # 加入访问过的节点
            for d in dirction:
                ni, nj = i + d[0], j + d[1]
                if (ni, nj) not in flag: # 判断有无走过
                     if dfs(ni, nj, word[1:]): return True
            flag.remove((i, j)) # 走完一定要回溯回状态
            return False
        
        dirction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        flag = []  # 标记走过的格子
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, word): 
                    return True
        return False

写法二： 使用 res 剪枝

这种写法的好处是

借助使用全局变量，不用考虑 dfs 的返回值如何设计，只需要考虑遍历方式即可

class Solution:
    res = False
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(x, y, word):
            if not word:  # 找到答案
                self.res = True
                return 
            if x < 0 or x >= n or y < 0 or y >= m or \ # 越界
               (x, y) in visited or \ # 访问过
               word[0] != board[y][x] or \ # 格子走不到
               self.res: # 剪枝
               return
            visited.add((x, y))
            for dx, dy in dirction:
                dfs(x + dx,y + dy, word[1:])
            visited.remove((x, y))

        dirction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = set()  # 访问矩阵
        n, m = len(board[0]), len(board)
        for i in range(n):
           for j in range(m):
               dfs(i, j, word)
        return self.res

Graceful Answer 【精妙写法】

参考自: Krahets-Leetcode 题解

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or \
               not 0 <= j < len(board[0]) or \
               board[i][j] != word[k]: 
                  return False # 判断都放在这里
            if k == len(word) - 1: return True
            tmp, board[i][j] = board[i][j], '/' # 直接修改原矩阵
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = tmp
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0): return True
        return False