【LeetCode】79. 单词搜索

链接：
https://leetcode.cn/problems/word-search/

思路：
利用深度优先遍历

深度优先遍历一般流程：
判断当前是否符合要求
若符合要求，则看更深一层是否符合要求
最后逐层向上返回

代码

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n, l = len(board), len(board[0]), len(word)
        def dfs(i, j, k):
            if k == l: return True
            if i < 0 or j < 0 or i >= m or j >= n or board[i][j] != word[k]:
                return False
            # 标记当前为已访问过
            board[i][j] = ''
            res = dfs(i + 1, j , k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            # 恢复当前标记
            board[i][j] = word[k]
            return res
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False