链接:
https://leetcode.cn/problems/word-search/
思路:
利用深度优先遍历
深度优先遍历一般流程:
判断当前是否符合要求
若符合要求,则看更深一层是否符合要求
最后逐层向上返回
代码
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n, l = len(board), len(board[0]), len(word)
def dfs(i, j, k):
if k == l: return True
if i < 0 or j < 0 or i >= m or j >= n or board[i][j] != word[k]:
return False
# 标记当前为已访问过
board[i][j] = ''
res = 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 res
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
标签:return,符合要求,dfs,单词,board,len,word,LeetCode,79
From: https://www.cnblogs.com/basilicata/p/17927786.html