79.Word Search

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        def dfs(r, c, k):
            if r < 0 or r >= m or c < 0 or c >= n or word[k] != board[r][c]:
                return False
            if k == len(word) - 1:
                return True
            tmp = board[r][c]
            board[r][c] = ''
            res = dfs(r+1, c, k+1) or dfs(r-1, c, k+1) or dfs(r, c+1, k+1) or dfs(r, c-1, k+1)
            board[r][c] = tmp
            return res

        for r in range(m):
            for c in range(n):
                if dfs(r, c, 0):
                    return True
        return False