题目描述

blablabla

样例

blablabla

算法1

() $O(n^2)$

blablabla

时间复杂度分析：blablabla

Python 代码

class Solution(object):
    def hasPath(self, matrix, string):
        """
        :type matrix: List[List[str]]
        :type string: str
        :rtype: bool
        """
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if self.dfs(matrix, string, 0, i, j):
                    return True
        return False

    def dfs(self, matrix, string, u, x, y):
        memo = matrix[x][y]
        if matrix[x][y] != string[u]:
            return False
        # 出口
        if u == len(string) - 1:
            return True
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        matrix[x][y] = '*'
        for i in range(4):
            a = x + dx[i]
            b = y + dy[i]
            if a >= 0 and a < len(matrix) and b >= 0 and b < len(matrix[a]):
                if self.dfs(matrix, string, u + 1, a, b):
                    return True

        matrix[x][y] = memo
        return False