Make writing a habit together! This is the 9th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

preface

Our community will continue to include Yi Gu (Netflix growth hacker, author of The Way to Interview for iOS, ACE professional fitness coach). Swift algorithm problem solving sorted into text version to facilitate everyone to learn and read.

We have updated 62 issues of LeetCode algorithm so far, and we will keep the update time and progress (Monday, Wednesday, Friday 9:00 am release). The content of each issue is not much, we hope you can read it on your way to work, there will be a great improvement in long-term accumulation.

Short step, no thousands of miles; No small streams, no rivers and seas, Swift community with you forward. If you have suggestions and comments welcome to leave a message at the end of the article, we will try our best to meet your needs.

Difficulty level: Medium

1. Describe

A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).

The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).

Now consider that there are obstacles in the grid. So how many different paths are there going to be from the top left to the bottom right?

Obstacles and empty positions in the grid are represented by 1 and 0 respectively.

Example 2.

Example 1

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0]] output: 2 explanation: there is an obstacle right in the middle of the 3x3 grid. There are two different paths from the upper left corner to the lower right corner: 1. Right -> Right -> Down -> Down 2. Down -> down -> right -> rightCopy the code

Example 2

Input: obstacleGrid = [[0,1],[0,0]] output: 1Copy the code

Constraints:

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1

3. The answer

class UniquePathsII {
    func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
        let m = obstacleGrid.count
        guard m > 0 else {
            return 0
        }
        
        let n = obstacleGrid[0].count
        guard n > 0 else {
            return 0
        }
    
        var dp = Array(repeating: Array(repeating: -1, count: n), count: m)
        
        return help(m - 1, n - 1.&dp, obstacleGrid)
    }
    
    fileprivate func help(_ m: Int._ n: Int._ dp: inout [[Int]], _ obstacleGrid: [[Int]]) -> Int {
        if m < 0 || n < 0 {
            return 0
        }
        if obstacleGrid[m][n] = = 1 {
            return 0
        }
        if m = = 0 && n = = 0 {
            return 1
        }
        if dp[m][n] ! = -1 {
            return dp[m][n]
        }
        
        dp[m][n] = help(m - 1, n, &dp, obstacleGrid) + help(m, n - 1.&dp, obstacleGrid)
        return dp[m][n]
    }
}
Copy the code
  • Main idea: 2D dynamic programming, using 2D array as cache to store computational data.
  • Time complexity: O(Mn)
  • Space complexity: O(Mn)

Leetcode-swift is a repository for solving problems of this algorithm

Click to go to LeetCode practice

About us

We are jointly maintained by Swift enthusiasts. We will share technical content based on Swift combat, SwiftUI and Swift foundation, as well as collect excellent learning materials.

The follow-up will also translate a large number of information to our public account, interested friends, can join us.