单词搜索-回溯79-python

没看答案，二维数组的回溯（类似棋盘问题）。

• 路径起始需要考虑所有可能的起始点。
• 下一个字母的搜索空间为当前匹配字母的上下左右，同时要设置防过界和重复检查。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        n = len(word)
        row, col = len(board), len(board[0])
        flag = False
        visited = [[False] * col for _ in range(row)]

        def backtrack(pos, pos_r, pos_c):
            nonlocal n, flag, row, col, word

            if flag: return
            
            if pos == n:
                flag = True
                return
            
            # 防止数组索引过界
            if pos_r < 0 or pos_r >= row or pos_c < 0 or pos_c >= col:
                return

            # 防止同一个单元格内的字母被重复使用
            if visited[pos_r][pos_c] == True:
                return
            
            if pos == 0:
                for r in range(row):
                    for c in range(col):
                        if flag: break
                        if board[r][c] == word[0]:
                            visited[r][c] = True
                            pos += 1
                            backtrack(pos, r, c+1)
                            backtrack(pos, r+1, c)
                            backtrack(pos, r-1, c)
                            backtrack(pos, r, c-1)
                            pos -= 1
                            visited[r][c] = False
            else:
                if word[pos] == board[pos_r][pos_c]:
                    visited[pos_r][pos_c] = True
                    pos += 1
                    backtrack(pos, pos_r, pos_c+1)
                    backtrack(pos, pos_r+1, pos_c)
                    backtrack(pos, pos_r-1, pos_c)
                    backtrack(pos, pos_r, pos_c-1)
                    pos -= 1
                    visited[pos_r][pos_c] = False
        
        backtrack(0, 0, 0)

        return flag