Standard DFS Python solution w/ memorization


  • 0

    It's a post-order DFS (Divide Conquer) that traverses all possible paths and caches traversed path to avoid duplicated recursion.

    class Solution(object):
        def longestIncreasingPath(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: int
            """
            self.directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
            visited = [[0 for j in xrange(0, len(matrix[0]))] for i in xrange(0, len(matrix))]
            cachePath = [[-1 for j in xrange(0, len(matrix[0]))] for i in xrange(0, len(matrix))]
            maxLength = 0
            for i in xrange(0, len(matrix)):
                for j in xrange(0, len(matrix[0])):
                    visited[i][j] = 1
                    maxLength = max(maxLength, self.dfsHelper(visited, cachePath, i, j, matrix[i][j], matrix))
                    visited[i][j] = 0
            return maxLength
            
        def dfsHelper(self, visited, cachePath, i, j, path, matrix):
            if i >= len(matrix) or i < 0 or j >= len(matrix[0]) or j < 0:
                return 0
            if cachePath[i][j] != -1:
                return cachePath[i][j]
            maxLength = 0
            for d in self.directions:
                newi, newj = i + d[0], j + d[1]
                if newi >= len(matrix) or newi < 0 or newj >= len(matrix[0]) or newj < 0:
                    continue
                if visited[newi][newj] == 0 and matrix[newi][newj] > path:
                    visited[newi][newj] = 1
                    maxLength = max(maxLength, self.dfsHelper(visited, cachePath, newi, newj,  matrix[newi][newj], matrix))
                    visited[newi][newj] = 0
    
            length = 1 + maxLength
            cachePath[i][j] = length
            return length

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.