Python recursive solution with cache - 54ms


  • 2
    G
    class Solution:
        # @param {integer[][]} obstacleGrid
        # @return {integer}
        def uniquePathsWithObstacles(self, obstacleGrid):
            if not len(obstacleGrid) or not len(obstacleGrid[0]):
                return 0
    
            cache = {}
            m, n = len(obstacleGrid) - 1, len(obstacleGrid[0]) - 1
    
            return self.findPath(obstacleGrid, m, n, cache)
    
        def findPath(self, obstacleGrid, m, n, cache):
            if (m, n) in cache:
                return cache[(m, n)]
            elif m < 0 or n < 0 or obstacleGrid[m][n] == 1:
                return 0
            elif m == 0 and n == 0:
                return 1
    
            cache[(m, n)] = self.findPath(obstacleGrid, m - 1, n, cache) + self.findPath(obstacleGrid, m, n - 1, cache)
    
            return cache[(m, n)]

Log in to reply
 

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