Challenge-me-python-solution-with-mimium-modification-based-on-unique-path-i


  • 0
    C

    Please challenge me with minimum modification (minimum edit distance) across these two questions

    class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [ [0] * n ] * m    
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    dp[i][j] = 1 
                elif i == 0:            # Row 1
                    dp[i][j] = dp[i][j - 1]
                elif j == 0:            # Col 1
                    dp[i][j] = dp[i - 1][j] 
                else:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                dp[i][j] *= (1 - obstacleGrid[i][j]) # We only consider obstacle here
        return dp[-1][-1]
    

    As a comparison, I also provide my python solution for "unique path 1"

    class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        dp = [ [1]*n ] * m  # Note, n = column num; m = row num 
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

  • 1
    T

    This is shorter, but yours is more readable.

    class Solution(object):
        def uniquePathsWithObstacles(self, M):
            m, n = len(M), len(M[0])
            dp = [[0]*n for i in range(m)]
            for i in range(m):
                for j in range( n):
                    if M[i][j] == 0:
                        if i == 0 and j == 0:
                            dp[i][j] = 1
                        else:
                            dp[i][j] = (i != 0) * dp[i-1][j] + (j != 0) * dp[i][j-1]
            return dp[-1][-1]

Log in to reply
 

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