Concise python solution with one dimensional array and avoid modifying matrix in place


  • 0
    C

    I just want to share my dp solution. The idea is almost the same as others but try to use less space and avoid modifying the matrix in place.

    class Solution(object):
        def uniquePathsWithObstacles(self, obstacleGrid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            m = len(obstacleGrid)
            n = len(obstacleGrid[0])
            dp_hor = [0] * (n + 1)
            dp_hor[0] = 1
            matrix = obstacleGrid
            # row by row to set the dp array
            for i in xrange(m):
                for j in xrange(1, n + 1):
                    if matrix[i][j - 1] == 1:
                        dp_hor[j] = 0
                    else:
                        dp_hor[j] = dp_hor[j] + dp_hor[j - 1]
                dp_hor[0] = 0
            return dp_hor[-1]
    

Log in to reply
 

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