Leetcode 2: path

Posted on | | Visitors: | views

根据我个人的总结，Leetcode上Array类问题中，easy主要是解决一维数组的搜索和排序问题，技巧要点是用pointer和hash表来减少loop成本；medium则是上升到了二维数组、矩阵和图的层次，至于技巧还需要慢慢摸索。在这里总结一些典型的路径搜索问题。

Unique Paths

  • Problem: A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?
  • Example: m = 3, n = 2, return 3. From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down; 2. Right -> Down -> Right; 3. Down -> Right -> Right
  • Link: https://leetcode.com/problems/unique-paths/
  • Answer:
    1
    2
    3
    4
    5
    # Comment: Easiest way is to use math

    class Solution:
        def uniquePaths(self, m, n):
            return int(math.factorial(m + n - 2) / math.factorial(m - 1) / math.factorial(n - 1))

Unique Paths II

  • Problem: A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. Now consider if some obstacles are added to the grids. How many unique paths would there be?
  • Example: Input [[0,0,0], [0,1,0], [0,0,0]], then output should be 2. The Explanation is: there is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down; 2. Down -> Down -> Right -> Right
  • Link: https://leetcode.com/problems/unique-paths-ii/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    # Comment: pure math cannot be use here, as the location of obstacles are random.
    # Fastest idea is recurrence, which is executable but with explosive complexity.
    # A better solution is dynamic programming.

    class Solution:
        def uniquePathsWithObstacles(self, obstacleGrid):
            m = len(obstacleGrid)
            n = len(obstacleGrid[0])
            obstacleGrid[0][0] = 1 - obstacleGrid[0][0]
            
            for i in range(1, n):
                if not obstacleGrid[0][i]:
                    obstacleGrid[0][i] = obstacleGrid[0][i-1]
                else:
                    obstacleGrid[0][i] = 0
                    
            for i in range(1, m):
                if not obstacleGrid[i][0]:
                    obstacleGrid[i][0] = obstacleGrid[i-1][0]
                else:
                    obstacleGrid[i][0] = 0
            
            for i in range(1, m):
                for j in range(1, n):
                    if not obstacleGrid[i][j]:
                        obstacleGrid[i][j] = obstacleGrid[i][j-1]+obstacleGrid[i-1][j]
                    else:
                        obstacleGrid[i][j] = 0
                        
            return obstacleGrid[-1][-1]

Minimum Path Sum

  • Problem: Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time.
  • Example: Input [[1,3,1], [1,5,1], [4,2,1]] (In fact, this is an weighted version of Probelm Unique Path), output 7 (1->3->1->1->1).
  • Link: https://leetcode.com/problems/minimum-path-sum/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    # Recurrence: possible but low-effiency
    # Dynamic Programming

    class Solution:
        def minPathSum(self, grid):
            m = len(grid)
            n = len(grid[0])

            for i in range(1, m):
                grid[i][0] += grid[i - 1][0]

            for i in range(1, n):
                grid[0][i] += grid[0][i - 1]

            for i in range(1, m):
                for j in range(1, n):
                    grid[i][j] += min(grid[i][j - 1], grid[i - 1][j])

            return grid[-1][-1]

Word Search

  • Problem: Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
  • Example: board = [[‘A’,’B’,’C’,’E’], [‘S’,’F’,’C’,’S’], [‘A’,’D’,’E’,’E’]], Given word = “ABCCED”, return true. Given word = “SEE”, return true. Given word = “ABCB”, return false.
  • Link: https://leetcode.com/problems/word-search/
  • Answer:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    # 优化回溯算法，来自Submission中的最强者，真的很厉害

    from collections import Counter
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 移动方向


    class Solution:
        def exist(self, board, word):
            m, n = len(board), len(board[0])
            bcnts = Counter(c for r in board for c in r)
            for w, w_cnt in Counter(word).items():  # 先通过个数检测是否不可能存在
                if w not in bcnts or w_cnt > bcnts[w]:
                    return False

            def backtrack(i, j, index):
                if index == len(word) - 1:  # 如果只有一个字母，即为True
                    return True
                # 标记为已访问
                board[i][j] = '*'
                for dx, dy in dirs:
                    next_i, next_j = i + dx, j + dy
                    # 先判断再进入，减少递归次数
                    if 0 <= next_i < m and 0 <= next_j < n and word[index + 1] == board[next_i][next_j] and backtrack(
                            next_i, next_j, index + 1):
                        return True
                board[i][j] = word[index]  # 再把标记过的还原
                return False

            for i in range(m):
                for j in range(n):
                    if board[i][j] == word[0] and backtrack(i, j, 0):
                        return True

            return False