单词搜索
Word Search
本机进度仅保存在当前浏览器
题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word，如果 word 存在于网格中，返回 true；否则返回 false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，同一个单元格内的字母不允许被重复使用。
示例：board 含路径 ["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]，word = "ABCCED" 返回 true。
解题思路
- 从每个格子尝试作为起点做 DFS：当前字符匹配则向四个方向扩展匹配下一个字符。
- 访问标记用原地修改（把当前格临时改成特殊字符）实现，回溯时恢复，省去 visited 数组。
- 任一起点成功即返回 true；配合"字符不匹配立即回退"的剪枝即可通过数据规模。
参考实现
查看参考实现Python · 建议先自行作答
def exist(board, word):
m, n = len(board), len(board[0])
def dfs(i, j, k):
# k 为待匹配的 word 下标
if board[i][j] != word[k]:
return False
if k == len(word) - 1:
return True
board[i][j] = '#' # 原地标记防重复访问
found = False
for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= x < m and 0 <= y < n and dfs(x, y, k + 1):
found = True
break
board[i][j] = word[k] # 回溯恢复
return found
return any(dfs(i, j, 0) for i in range(m) for j in range(n))