79. 单词搜索

79. 单词搜索
剑指 Offer 12. 矩阵中的路径

题目

题解

就是普通的DFS，其实也不难，就是写得太慢，多练练就好

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        def dfs(target_str, pos=None):
            # 如果搜到最后字符串已经为空，说明搜索成功
            if target_str == '':
                return True
            x, y = pos
            move_step = [(0, 1), (0, -1), (1, 0), (-1, 0)]
            target_char = target_str[0]
            if 0 <= x < m and 0 <= y < n and S[x][y] == target_char:
                S[x][y] = 'None'
                # 把 S[i][j] 处标记为不可再访问
                for dx, dy in move_step:
                    i, j = x+dx, y+dy
                    if dfs(target_str[1:], pos=(i, j)):
                        return True
                # 搜完之后记得改回来
                S[x][y] = target_char
            else:
                return False
        S=board
        m, n = len(S), len(S[0])
        for i in range(m):
            for j in range(n):
                if dfs(word, pos=(i, j)):
                    return True
                # 如果遍历所有初始点都没搜到，返回 FALSE
        return False