My accepted python solution


  • 0
    S
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if obstacleGrid[-1][-1] == 1:
            return 0
            
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        result = [ [0 for i in range(n)] for i in range(m) ]
        
        result[m-1][n-1] = 1
        
        for i in range(m-2,-1,-1):
            if obstacleGrid[i][n-1] == 1:
                break
            else:
                result[i][n-1] = 1
        
        for j in range(n-2,-1,-1):
            if obstacleGrid[m-1][j] == 1:
                break
            else:
                result[m-1][j] = 1
                
        for i in range(m-2,-1,-1):
            for j in range(n-2,-1,-1):
                if obstacleGrid[i][j] == 1:
                    continue
                else:
                    result[i][j] = result[i+1][j] + result[i][j+1]
        return result[0][0]
    

    The key idea here is to maintain a new result matrix, which is to store the number of paths from each point to the end point.


Log in to reply
 

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