剣指offer——12.行列内のパス

問題:ある文字列のすべての文字を含むパスがマトリクスに存在するかどうかを判断する関数を設計してください.パスは、マトリクス内の任意の格子から開始できます.各ステップは、マトリクス内で左、右、上、下に1つの格子を移動できます.1つのパスがマトリクス内の格子を通過した場合、そのパスは格子に入ることができません.例えば、a b c e s f c s a d e行列には「bcced」という文字列の経路が含まれているが、行列の最初の文字bが行列の最初の行の2番目の格子を占めた後、経路が再び格子に入ることができないため、行列には「abcb」という経路が含まれていない.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
       		 #i，j         ， i、j       ，    board     word   k      
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
            if k == len(word) - 1: return True #             ，  true，        
            tmp, board[i][j] = board[i][j], ''     #       tmp，            ，         ‘’   
            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] = tmp #  tmp        board[i][j]   。
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0): return True  #           ，  false
        return False