面试150 单词搜索

思路

使用深搜+回溯的方法，通过遍历每个起始点，对每个位置递归搜索其上下左右四个方向的字符，尝试与单词逐个匹配。使用visited数组标记已访问的位置，避免重复使用同一个格子。在每次递归结束后，撤回标记，结束回溯。当成功匹配到单词的所有字符串时返回True,否则继续搜索其他路径，直到走完所有路径。

class Solution: def exist(self, board: List[List[str]], word: str) -> bool: m=len(board) n=len(board[0]) visited=[[False]*n for _ in range(m)] def dfs(i,j,k): if k==len(word): return True if i<0 or i>=m or j<0 or j>=n or board[i][j]!=word[k] or visited[i][j]:#访问过的就不管了 return False visited[i][j]=True dis=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) visited[i][j]=False return dis for i in range(m): for j in range(n): if dfs(i,j,0):  return True return False