Leetcode: Unique Paths II

Unique Paths II



Similar Problems:


Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3×3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/unique-paths-ii
## Basic Ideas: dynamic programming
##  Very similar to https://code.dennyzhang.com/unique-paths
##
##              f(i, j) = if it's obstacle, 0
##                        else: f(i-1, j) + f(i, j-1)
##
## Complexity: Time O(m*n), Space O(m*n)
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        row_count = len(obstacleGrid)
        if row_count == 0: return 0
        col_count = len(obstacleGrid[0])
        # use default values to simplify the code
        matrix = [[0 for x in xrange(col_count)] for y in xrange(row_count)]

        matrix[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
        # first row
        i = 0
        for j in range(1, col_count):
            if obstacleGrid[i][j] == 0: matrix[i][j] = matrix[i][j-1]

        # first column
        j = 0
        for i in range(1, row_count):
            if obstacleGrid[i][j] == 0: matrix[i][j] = matrix[i-1][j]

        # others
        for i in range(1, row_count):
            for j in range(1, col_count):
                if obstacleGrid[i][j] == 0:
                    matrix[i][j] = matrix[i-1][j] + matrix[i][j-1]

        return matrix[-1][-1]
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.