79. 单词搜索【dfs + 回溯visit + 遍历起点】

分析

用dfs + visit + 回溯的思路
然后找到合适的入口
再看看下一个上下左右的位置拿个是适合放的（这里用visit回溯）
dfs遍历所有能走的位置，只要有一个子dfs返回True
那么整个就是True的，如果没有返回True
很遗憾，那只能是False
最后如果能去到最后一个位置即可返回

ac code

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])     
        k = len(word)


        # dfs + 回溯
        def dfs(r, c, idx):
            

            if idx == k - 1:
                return True
            
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < m and 0 <= nc < n and word[idx + 1] == board[nr][nc] and visit[nr][nc] is False:
                    visit[nr][nc] = True
                    temp = dfs(nr, nc, idx + 1)
                    if temp: return True
                    visit[nr][nc] = False
            
            return False
        
        # 遍历每个起点
        for i in range(m):
            for j in range(n):
                visit = [[False] * n for _ in range(m)]
                if board[i][j] == word[0]:
                    visit[i][j] = True
                    if dfs(i, j, 0):  return True
        
        return False

总结

dfs的参数记录当前的位置以及当前的已放的最后一个元素的idx
成功条件就是到达最后一个索引