Accepted simple Python in-place solution


  • 8
    X

    As below. Any comments on how to make it shorter? Thx!

    class Solution:
        # @param obstacleGrid, a list of lists of integers
        # @return an integer
        def uniquePathsWithObstacles(self, obstacleGrid):
            m = len(obstacleGrid)
            n = len(obstacleGrid[0])
            obstacleGrid[0][0] = 1 - obstacleGrid[0][0]
            
            for i in range(1, n):
                if not obstacleGrid[0][i]:
                    obstacleGrid[0][i] = obstacleGrid[0][i-1]
                else:
                    obstacleGrid[0][i] = 0
                    
            for i in range(1, m):
                if not obstacleGrid[i][0]:
                    obstacleGrid[i][0] = obstacleGrid[i-1][0]
                else:
                    obstacleGrid[i][0] = 0
                    
            for i in range(1, m):
                for j in range(1, n):
                    if not obstacleGrid[i][j]:
                        obstacleGrid[i][j] = obstacleGrid[i][j-1]+obstacleGrid[i-1][j]
                    else:
                        obstacleGrid[i][j] = 0
                        
            return obstacleGrid[-1][-1]

  • 15
    S
    class Solution:
    # @param obstacleGrid, a list of lists of integers
    # @return an integer
    def uniquePathsWithObstacles(self, obstacleGrid):
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        ResGrid = [[0 for x in range(n+1)] for x in range(m+1)]
        ResGrid[0][1] = 1
    
        for i in range(1, m+1):
            for j in range(1, n+1):
                if not obstacleGrid[i-1][j-1]:
                    ResGrid[i][j] = ResGrid[i][j-1]+ResGrid[i-1][j]
    
        return ResGrid[m][n]

  • 0
    L
    This post is deleted!

  • 0
    O

    wow nice thoughts for saving the memory space!
    I also couldn't find a better way to update the first column and first raw more concisely.
    Hope to see someone handling the problem in place more elegantly too A__A!


  • 5
    T
    def uniquePathsWithObstacles(self, obstacleGrid):
            M, N = len(obstacleGrid), len(obstacleGrid[0])
            dp = [1] + [0] * (N-1)
            for i in range(M):
                for j in range(N):
                    if obstacleGrid[i][j] == 1:
                        dp[j] = 0
                    elif j > 0:
                        dp[j] += dp[j-1]
            return dp[N-1]

  • 0
    T

    The answer upstairs seems to be a cute method for saving the memory. On each of first iteration, the dp(1-dimension list) itself is equal to dp[i-1](2-dimension list) before adding operation and dp[i](2-dimension list) after process, how wonderfu!


Log in to reply
 

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