class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        
        def dfs(i,j,word, visited):
            
            if board[i][j] == word:
                return True
            
            if word[0] != board[i][j]:
                return False
            
            key = str(i) + ',' + str(j) + ',' + word
            if key in memo:
                return memo[key]
            
            dirs = [(0,1),(0,-1),(-1,0),(1,0)]
            for di,dj in dirs:
                newi,newj = i+di, j+dj
                if 0<=newi<m and 0<=newj<n and not visited[newi][newj]:
                    visited[newi][newj] = True
                    if dfs(newi,newj,word[1:],visited):
                        memo[key] = True
                        return memo[key]
                    visited[newi][newj] = False
            memo[key] = False
            return memo[key]
        
        memo = {}
        
        m = len(board)
        n = len(board[0])
        for i in range(m):
            for j in range(n):
                visited = [[False]*n for _ in range(m)]
                visited[i][j] = True
                if dfs(i,j,word, visited):
                    return True
        
        return False