79. 单词搜索
难度中等585收藏分享切换为英文关注反馈
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
提示：
-
board和word中只包含大写和小写英文字母。 1 <= board.length <= 2001 <= board[i].length <= 2001 <= word.length <= 10^3
思路
利用深度优先遍历， 先找到入口，之后对其所有可能下一步进行搜索，找到符合条件的则返回True， 若找到途中没有符合条件的则返回False
自定义函数：
-
judge_aviliable(i, j, char)判断i, j下标是否可用，可用的标准如下- 在矩形范围内
- 没有被访问过
- 该点在
board中的值恰好是当前需要匹配的word[index]值
-
get_next(i， j, char):获取i, j下标的相邻且符号为char的相邻位置 -
dfs(i, j, index)使用深度优先遍历，遍历图表，若存在word路径则返回true， 不存在则返回False
注意点
对一个点的邻接点进行遍历时，若该点有多个符合条件的邻接点，则只要其中之一返回结果为
True， 即可返回True在找第一个入口地址时，没必要单独处理，直放在dfs中进行一次特判，后面的步骤就都一样了，我的代码中的处理方式是：第一次进入dfs时设置
i=j=-1，通过这个来判断是不是第一次进入dfs记录某一个点是否被访问过，需要设置
visited=1,但是记得推出递归栈时一定要把visited设置回0， 避免从其他路径走过来时不能访问之前走错的点。
代码
- python3 版本
class Solution:
def exist(self, board, word: str) -> bool:
if len(board) == 0: return False
if word == '': return True
m, n = len(board), len(board[0])
visited = [[0 for j in range(n)] for i in range(m)]
def judge_aviliable(i, j, char):
return i >=0 and i <m and j >=0 and j < n and visited[i][j] == 0 and board[i][j] == char
def get_next(i, j, char):
net = []
if judge_aviliable(i + 1, j, char): net.append([i + 1, j])
if judge_aviliable(i, j + 1, char): net.append([i, j + 1])
if judge_aviliable(i - 1, j, char): net.append([i - 1, j])
if judge_aviliable(i, j - 1, char): net.append([i, j - 1])
return net
def dfs(i, j, index):
if index == len(word): return True
if i == -1 and j == -1: #
net = []
for i in range(m):
for j in range(n):
if board[i][j] == word[index]: net.append([i, j])
else:
net = get_next(i, j, word[index])
if not net: return False
res = False
for next_i, next_j in net:
visited[next_i][next_j] = 1
res = res or dfs(next_i, next_j, index + 1)
visited[next_i][next_j] = 0
return res
return dfs(-1, -1, 0)
