79 Word Search

https://leetcode.com/problems/word-search/

solution

• 通过修改访问标记的方式回溯

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])

        for i in range(m):
            for j in range(n):
                if self.dfs(i, j, 0, board, word):
                    return True
        return False

    def dfs(self, x, y, k, board, word):
        if k == len(word):
            return True

        if x < 0 or x >= len(board) or y < 0 or y >= len(board[0]) or board[x][y] != word[k]:
            return False

        mem = board[x][y]
        board[x][y] = '*'
        res = self.dfs(x+1, y, k+1, board, word) or self.dfs(x, y+1, k+1, board, word) or self.dfs(x-1, y, k+1, board, word) or self.dfs(x, y-1, k+1, board, word)
        board[x][y] = mem
        return res

时间复杂度：O(mn4^word) 空间复杂度：O(4^word)

follow up

212 Word Search II