class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        #TC: O(mn*len(word))
        #SC: O(len(word))
        m = len(board)
        n = len(board[0])

        DirList = [[0,1],[0,-1],[1,0],[-1,0]]

        def dfs(x0, y0, idx):
            if idx == len(word)-1:
                return True

            Bool = False

            for Dir in DirList:
                x = x0 + Dir[0]
                y = y0 + Dir[1]

                if 0 <= x < m and 0 <= y < n and board[x][y] == word[idx+1]:
                    board[x][y] = '#'
                    Bool = Bool or dfs(x, y, idx+1)
                    board[x][y] = word[idx+1]

            return Bool

        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    board[i][j] = '#'
                    Bool = dfs(i,j,0)
                    board[i][j] = word[0]
                    if Bool:
                        return True
        return False