【LeetCode】0079&剑指Offer12 单词搜索&矩阵中的路径

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

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

# -*- coding:utf-8 -*-
class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        n = len(board)
        m = len(board[0])
        def dfs(i, j, index):
            mp[i][j] = False
            if index == len(word):
                return True
            for ii, jj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                if 0 <= i + ii < n and 0 <= j + jj < m and board[i + ii][j + jj] == word[index] and mp[i + ii][j + jj]:
                    if dfs(i + ii, j + jj, index + 1):
                        return True
            mp[i][j] = True
            return False
        for i in range(n):
            for j in range(m):
                if board[i][j] == word[0]:
                    mp = [[True] * m for i in range(n)]
                    if dfs(i, j, 1):
                        return True
        return False
if __name__ == '__main__':
    board = [
        ['A', 'B', 'C', 'E'],
        ['S', 'F', 'C', 'S'],
        ['A', 'D', 'E', 'E']
    ]
    word = 'ABCB'
    print(Solution().exist(board, word))

思路：动归回溯做的都有点快忘了基础的了。。这道题深度优先遍历，分别向上下左右遍历寻找目标字符串。