DFS with memoization in python


  • 0
    Z
    class Solution(object):
        def longestIncreasingPath(self, matrix):
            
            def longestIncreasingPathHelper(matrix, table, i, j):
                if table[i][j]:
                    return table[i][j]
                pathLength = 1
                if i-1 >= 0 and matrix[i-1][j] > matrix[i][j]:
                    pathLength = max(pathLength,
                        longestIncreasingPathHelper(matrix, table, i-1, j) + 1)
                if i+1 < len(matrix) and matrix[i+1][j] > matrix[i][j]:
                    pathLength = max(pathLength,
                        longestIncreasingPathHelper(matrix, table, i+1, j) + 1)
                if j-1 >= 0 and matrix[i][j-1] > matrix[i][j]:
                    pathLength = max(pathLength,
                        longestIncreasingPathHelper(matrix, table, i, j-1) + 1)
                if j+1 < len(matrix[i]) and matrix[i][j+1] > matrix[i][j]:
                    pathLength = max(pathLength,
                        longestIncreasingPathHelper(matrix, table, i, j+1) + 1) 
                table[i][j] = pathLength
                return pathLength
            
            if not matrix:
                return 0
            table = [[0] * len(row) for row in matrix]
            max_path = 0
            for i in range(len(matrix)):
                for j in range(len(matrix[i])):
                    max_path = max(max_path, longestIncreasingPathHelper(matrix, table, i, j))
            return max_path

Log in to reply
 

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