R2-回溯:DFS+剪枝.
class Solution:def exist(self, board: List[List[str]], word: str) -> bool:#回溯经典问题：DFS+剪枝解决m=len(board)n=len(board[0])def dfs(i,j,k):#3种剪枝策略if not 0<=i<m or not 0<=j<n or board[i][j]!=word[k]:return Falseif k==len(word)-1:return Trueboard[i][j]=''#4条路，其中有一条是往回走的ret=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 ret#每一个格子都能出发for i in range(m):for j in range(n):if dfs(i,j,0):return Truereturn False
ps:
k神
