题目
- 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
题解：回溯
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
if not board: # 边界条件
return False
for i in range(len(board)):
for j in range(len(board[0])):
if self.backtrack(board, i, j, word):#表示从当前位置 (i, j) 开始，搜索能否匹配整个单词 word。
return True
return False
def backtrack(self, board, i, j, word):
if len(word) == 0: # 如果单词已经检查完毕
return True
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or word[0] != board[i][j]: # 如果路径出界或者矩阵中的值不是word的首字母，返回False
return False
tmp = board[i][j] # 保存当前位置的值
board[i][j] = '0' #做选择
#将四个方向的搜索结果进行合并。如果其中任意一个方向的搜索返回 True，则表示找到了满足条件的路径，将 res 设置为 True。
res = self.backtrack(board,i+1,j,word[1:]) or self.backtrack(board,i-1,j,word[1:]) or self.backtrack(board,i,j+1,word[1:]) or self.backtrack(board, i, j-1, word[1:]) # 上下左右四个方向搜索，递归
board[i][j] = tmp # 标记过的点恢复原状，以便进行下一次搜索，撤销选择
return res#res 是一个布尔值变量，用于存储回溯搜索的结果。它表示在当前位置 (i, j) 上，是否存在一条路径可以匹配整个单词 word。