Clean python code


  • 1

    The main idea is using DFS to search the longest increasing path from each point, and then cache the result for other paths passing it to use it.

    class Solution(object):
        def search(self, i, j, val, m, n, matrix, r):
            if r[i][j] is not None:
                return r[i][j]
    
            length = 0
            for x, y in ((0, -1), (-1, 0), (0, 1), (1, 0)):
                ii, jj = i + x, j + y
                if 0 <= ii < m and 0 <= jj < n and matrix[ii][jj] > val:
                    v = matrix[ii][jj]
    
                    matrix[ii][jj] = float('-inf')
                    length = max(self.search(ii, jj, v, m, n, matrix, r), length)
                    matrix[ii][jj] = v
    
            r[i][j] = length + 1
            return r[i][j]
    
        def longestIncreasingPath(self, matrix):
            if not matrix:
                return 0
    
            m, n = len(matrix), len(matrix[0])
            r = [[None] * n for _ in xrange(m)]
    
            return max(
                self.search(i, j, val, m, n, matrix, r)
                for i, row in enumerate(matrix)
                for j, val in enumerate(row)
            )

Log in to reply
 

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