单词搜索
https://leetcode.cn/problems/word-search/description/
-
深度优先搜索解法。
-
时间复杂度：一个非常宽松的上界为 \(O(MN⋅3^L)\)，其中 M,N 为网格的长度与宽度，L 为字符串 word 的长度。在每次调用函数 check 时，除了第一次可以进入 4 个分支以外，其余时间我们最多会进入 3 个分支（因为每个位置只能使用一次，所以走过来的分支没法走回去）。由于单词长为 L，故 check(i,j,0) 的时间复杂度为 \(O(3^L)\)，而我们要执行 \(O(MN)\) 次检查。然而，由于剪枝的存在，我们在遇到不匹配或已访问的字符时会提前退出，终止递归流程。因此，实际的时间复杂度会远远小于 \(Θ(MN⋅3^L)\)。
-
空间复杂度：\(O(MN)\)。我们额外开辟了 \(O(MN)\) 的 visited 数组，同时栈的深度最大为 \(O(min(L,MN)\))。
-
搜就完了，错误点在于忘了回溯的时候更新visited=0了，会导致其他方案搜不到
-
visited 数组的恢复：在深度优先搜索（DFS）中，当你回溯时，应该将 visited[i][j] 重新设置为 0，以便其他路径可以重新访问这个单元格。否则，可能会导致某些路径被错误地标记为已访问，从而影响结果。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
row=len(board)
col=len(board[0])
for i in range(row):
for j in range(col):
if board[i][j] == word[0]:
pos=0
visited = [[0]*col for _ in range(row)]
if self.dfs(board, visited,i,j,pos,word)==1:
return True
return False
def dfs(self,board,visited,i,j,pos,word):
if pos == len(word):
return 1
if i<0 or i>=len(board) or j<0 or j>=len(board[0]):
return 0
if board[i][j] == word[pos] and visited[i][j]==0:
visited[i][j]=1
if self.dfs(board,visited,i+1,j,pos+1,word) == 1:
return 1
if self.dfs(board,visited,i-1,j,pos+1,word) ==1:
return 1
if self.dfs(board,visited,i,j+1,pos+1,word)==1:
return 1
if self.dfs(board,visited,i,j-1,pos+1,word)==1:
return 1
visited[i][j]=0
else:
return 0