本文共 4842 字，大约阅读时间需要 16 分钟。

【题目描述】 给定一个 m x n 的 二维字符网格 board 和一个字符串单词 word 。 如果 word 存在于网格中，返回 true ；否则，返回 false 。

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

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

【解题思路】

本问题是典型的矩阵搜索问题，可使用 深度优先搜索（DFS）+ 剪枝 解决。

• 深度优先搜索： 可以理解为暴力法遍历矩阵中所有字符串可能性。DFS通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
• 剪枝： 在搜索中，遇到 这条路不可能 和 目标字符串匹配成功 的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为 可行性剪枝 。
  【通俗一点就是：A的下元素不匹配，下路就没有走的必要了，没有往下搜索的必要了；A的上元素越界，上路就没有走的必要了；A的右元素匹配，可以继续走；A的左元素越界，左路就没有走的必要了】
  

【图表说明】

目标字符 word = "A B C C E D"的检测流程如下： 对于目标字符 word[0]=A，在board的二维循环中依次查找

board[0][0]=‘A’，进入DFS，board[0][0]=word[0]=A 匹配成功 开始递推工作：

1. ① 令board[0][0]=A为空
   ② 开始搜索元素（下/上/右/左）
   下： 字符S不匹配B
   上： i=-1，i越界
   右：board[0][1]=word[1]=B 匹配成功
2. ① 令board[0][1]=B为空
   ② 开始搜索元素
   下： 字符F不匹配C
   上： i=-1，i越界
   右： board[0][2]=word[2]=C，匹配成功
3. ① 令board[0][2]=C为空
   ② 开始搜索元素
   下： board[1][2]=word[3]=C 匹配成功
4. ① 令board[1][2]=C为空
   ② 开始搜索元素
   下： board[2][2]=word[4]=E 匹配成功
5. ① 令board[2][2]=E为空
   ② 开始搜索元素（下/上/右/左）
   下： i=3，i越界
   上： 空字符’ '不匹配D
   右： 字符E不匹配D
   左： board[2][1]=word[5]=D 匹配成功
   ========= word匹配结束 =========
   .

开始回溯：

• 左元素 board[2][1]=D 递归完毕 （这轮初始值为 E）return True
• 下元素 board[2][2]=E 递归完毕（这轮初始值为 C）return True
• 下元素 board[1][2]=C 递归完毕（这轮初始值为 C）return True
• 右元素 board[0][2]=C 递归完毕（这轮初始值为 B）return True
• 右元素 board[0][1]=B 递归完毕（这轮初始值为 A）return True

注：匹配成功返回的True,是在word最后一个字符匹配结束后回溯返回的（即青色背景的T 是在回溯过程中才画上的）

【源代码】

class Solution:    def exist(self, board: List[List[str]], word: str) -> bool:        def dfs(i, j, k):        	# 2.终止条件            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            # 3.递推工作            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] = word[k]            return res		# 1.主函数        for i in range(len(board)):            for j in range(len(board[0])):                if dfs(i, j, 0): return True        return False'''作者：jyd链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/'''

注：主函数为什么要设置双循环 遍历board所有字符？ 为什么不能直接if dfs(0, 0, 0): return True

==> 因为不是每个目标字符word都是从board(0,0)开始，可能board(1,1)等

【打印版】

对回溯过程不太理解的，看这个应该比较清楚点

def exist(board, word):    def dfs(i, j, k):        # 2.终止条件        if not 0 <= i < len(board):             print('i=%d,i越界'%i)            return False        elif not 0 <= j < len(board[0]):            print('j=%d,j越界'%j)            return False        elif board[i][j] != word[k]:            print('字符%s不匹配%s'%(board[i][j],word[k]))            return False        # 所有中止条件都不满足,那么当前字符匹配成功        print('board[%d][%d]=word[%d]=%s'%(i,j,k,word[k]))        print('=== 匹配成功 ===')        # 最后一个字符        if k == len(word) - 1:            print('这是最后一个字符,word匹配结束')            return True                # 3.开始递推工作        # 标记当前矩阵元素        print('\n令board[%d][%d]=%s为空'%(i,j,board[i][j]))        board[i][j] = ''    # 将 board[i][j] 修改为 空字符'',代表此元素已访问过                # 搜索元素(下/上/右/左)        res = 1 # 初始化为1        # 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)        if dfs(i + 1, j, k + 1):            print('下元素board[%d][%d]=%s递归完毕'%(i+1,j,board[i+1][j]),end='\n')        elif dfs(i - 1, j, k + 1):            print('上元素board[%d][%d]=%s递归完毕'%(i-1,j,board[i-1][j]),end='\n')        elif dfs(i, j + 1, k + 1):            print('右元素board[%d][%d]=%s递归完毕'%(i,j+1,board[i][j+1]),end='\n')        elif dfs(i, j - 1, k + 1):            print('左元素board[%d][%d]=%s递归完毕'%(i,j-1,board[i][j-1]),end='\n')        else:   # 以上都没有就为0            res=0        board[i][j] = word[k]        print('这轮初始值为',board[i][j])        print('res =',res)        return res    # exist函数的主函数        # 1.递归参数    print('len(board)=',len(board))    print('len(board[0])=',len(board[0]))    for i in range(len(board)):        for j in range(len(board[0])):            print(i,'\t',j)            if dfs(i, j, 0):                return True    return Falseboard = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]word = "ABCCED"print(exist(board,word))

len(board)= 3len(board[0])= 40        0board[0][0]=word[0]=A=== 匹配成功 ===令board[0][0]=A为空字符S不匹配B				# 下i=-1,i越界				# 上board[0][1]=word[1]=B	# 右=== 匹配成功 ===			# A搜了3次令board[0][1]=B为空字符F不匹配C				# 下i=-1,i越界				# 上board[0][2]=word[2]=C	# 右=== 匹配成功 ===			# B搜了3次令board[0][2]=C为空		board[1][2]=word[3]=C	# 下=== 匹配成功 ===			# C搜了1次令board[1][2]=C为空board[2][2]=word[4]=E	# 下=== 匹配成功 ===			# C搜了1次令board[2][2]=E为空i=3,i越界				# 下字符不匹配D				# 上字符E不匹配D				# 右board[2][1]=word[5]=D	# 左=== 匹配成功 ===			# E搜了4次这是最后一个字符,word匹配结束左元素board[2][1]=D递归完毕这轮初始值为Eres = 1下元素board[2][2]=E递归完毕这轮初始值为Cres = 1下元素board[1][2]=C递归完毕这轮初始值为Cres = 1右元素board[0][2]=C递归完毕这轮初始值为Bres = 1右元素board[0][1]=B递归完毕这轮初始值为Ares = 1True

转载地址：http://mfjii.baihongyu.com/