Leetcode 79. 单词搜索

心路历程：

做完这道题才发现是回溯，一开始想的是递归，判断完第i个字符后，只需要挨个判断第i+1个字符在不在第i个字符的邻域。后来发现由于不能重复使用元素，所以需要维护一个visited列表，并且在遍历所有可能组合的时候还得撤回之前的选择。
回过头来从回溯的角度思考这个问题：每个边（路径）可以看作是选择哪个字母，候选集合就是当前邻域（结点）。相当于‘选哪个’的问题。

注意的点：

1、题目中要求字符不能重复选择，因此需要维护一个visited，并且需要在遍历结束后撤销选择。
2、debug时可以打印每个结点的值来看递归函数执行的正确性。

解法： 回溯

因为一开始以为是DP问题，所以为了后面用cache装饰器方便而参数化了递归函数的输入，写完后发现其实代码可以简化，可以把首字母的可选邻域看作整个board。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 递归

        # 获取第一个单词的所有可能位置和其邻域
        first = word[0]
        pos_first = []
        m = len(board)
        n = len(board[0])
        for i_ in range(m):
            for j_ in range(n):
                if board[i_][j_] == first:
                    pos_first.append((i_, j_))
        if not pos_first:
            return False
        visited = []
        # print(pos_first)
        # @cache 回溯不能cache
        def dfs(i, j, k):  # 上一个字母的位置是i,j; 此时判断第k个字母在不在其i,j的邻域中
            assert k > 0
            if k == len(word):
                return True
            nonlocal m, n, board
            # 先求i,j的邻域
            linyu = []
            if i + 1 <= m - 1:
                linyu.append([i+1, j])
            if i - 1 >= 0:
                linyu.append([i-1, j])
            if j + 1 <= n - 1:
                linyu.append([i, j+1])
            if j - 1 >= 0:
                linyu.append([i, j-1])
            flag = False
            for eve in linyu:
                if board[eve[0]][eve[1]] == word[k] and (eve[0], eve[1]) not in visited:
                    visited.append((eve[0], eve[1]))
                    flag = flag or dfs(eve[0], eve[1], k+1)
                    visited.pop()
            # print(i,j,k,flag, linyu, visited)
            return flag

        res = False
        for each_init in pos_first:
            visited.append((each_init[0], each_init[1])) # 因为不能重复选择字母
            res = res or dfs(each_init[0], each_init[1], 1)
            visited.pop()

        return res