LC79 Word Search

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # time O( M * N * 4^L ), where M*N is size of board, L is length of target word. space O(L)
        if not board:
            return False
        row = len(board)
        col = len(board[0])
        # why using two for loop?  i,j stand for start point 
        for i in range(row):
            for j in range(col):
                if self.dfs(i,j,word,board):
                    return True
        return False
    def dfs(self,x,y,w,brd):
    # termination condition: all chars in word have been visited and appeared in the board
        if len(w) == 0:
            return True
    # set up boundry to return False: 1. out of board 2. not same as word[0]
        if not (0<=x< len(brd) and 0<=y< len(brd[0]) and w[0]==brd[x][y]):
            return False
        # save char at board[x][y] to temp and set it to '#', then go to next recursion at 4 direction;
        tmp = brd[x][y]
        brd[x][y] = '#'
        res = self.dfs(x+1,y,w[1:],brd)  or self.dfs(x-1,y,w[1:],brd) or self.dfs(x,y+1,w[1:],brd) or self.dfs(x,y-1,w[1:],brd)
        brd[x][y] = tmp
        return res