剑指 Offer 12. 矩阵中的路径(回溯 DFS)

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
示例 1：
输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出：true

示例 2：
输入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
输出：false

思路分析

一道非常经典的矩阵搜索题。

直接回溯。

1.确定循环体

肯定是要遍历矩阵中的每一个格子，以每一个格子为起点向外搜索。

for i in range(len(board)):for j in range(len(board[0])):

2.确定回溯体参数

显然需要当前遍历的格子下标i和j，还需要当前遍历的单词下标k。
def dfs(i,j,k):

3.确定回溯体

在回溯的过程中，如果遇到边界，则立即回退，遇到不符合单词的字符，也立即回退。

if not 0<=i<len(board) or not 0<= j<len(board[0])  or board[i][j] != word[k]:return False           

当前遍历单词的下标k如果遍历到最后了，说明此时找到了完整的单词：

if len(word)-1 == k:return True

后面就是连续的三步，
1，首先将所有遍历过的格子都弄成空，防止重复遍历。
2. 回溯寻找当前格子的四周。
3. 回退的时候将变空的格子变回原来的数值。

            board[i][j] = ' 'res = dfs(i-1,j,k+1) or dfs(i,j-1,k+1) or dfs(i+1,j,k+1) or dfs(i,j+1,k+1)board[i][j] = word[k]

完整代码

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:# k为当前word遍历的下标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 Falseif len(word)-1 == k:return Trueboard[i][j] = ' 'res = dfs(i-1,j,k+1) or dfs(i,j-1,k+1) or dfs(i+1,j,k+1) or dfs(i,j+1,k+1)board[i][j] = word[k]return res for i in range(len(board)):for j in range(len(board[0])):if dfs(i,j,0):return Truereturn False