short and sweet Python solution, in-place, DP, AC 62ms


  • 0
    V
    class Solution:
        def uniquePathsWithObstacles(self, obstacleGrid):
            """
            :type obstacleGrid: List[List[int]]
            :rtype: int
            """
            if (not obstacleGrid) or obstacleGrid[0][0]:
                return 0
            
            obstacleGrid[0][0] = 1
            m, n = len(obstacleGrid), len(obstacleGrid[0])
            
            for i in range(1,m):
                obstacleGrid[i][0] = obstacleGrid[i-1][0] * (1-obstacleGrid[i][0])
                
            for j in range(1,n):
                obstacleGrid[0][j] = obstacleGrid[0][j-1] * (1-obstacleGrid[0][j])
                
            for i in range(1,m):
                for j in range(1,n):
                    obstacleGrid[i][j] = (1-obstacleGrid[i][j])*(obstacleGrid[i-1][j]+obstacleGrid[i][j-1])
            
            return obstacleGrid[-1][-1]
    

Log in to reply
 

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