65、矩阵中的路径

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def isValid(i, j):
            return 0 <= i < m and 0 <= j < n

        def dfs(i, j, visited):
            if len(visited) >= len(word):
                return True
            for dx, dy in delt:
                x, y = i + dx, j + dy
                if isValid(x, y) and (x, y) not in visited and word[len(visited)] == board[x][y]:
                    visited.add((x, y))
                    if dfs(x, y, visited):
                        return True
                    visited.remove((x, y))
            return False
                
        m, n = len(board), len(board[0])
        delt = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        for i in range(m):
            for j in range(n):
                visited = set()
                if board[i][j] == word[0]:
                    visited.add((i, j))
                    if dfs(i, j, visited):
                        return True
        return False