Leetcode # 221. Maximal Square

https://leetcode.com/problems/maximal-square

Solution

square := {top, bottom, left, right}
side_length(square) := (bottom – top + 1) == (right – left + 1)
dp[i][j] := side length of the maximum square whose bottom right corner is (i, j)

m := len(matrix)
n := len(matrix[0])

Time Complexity: O(m * n)
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maximalSquare(self, matrix: List[List[str]]) -> int:
    prev_dp = [ord(c) - 48 for c in matrix[0]]
    max_len = max(prev_dp)
    m, n = len(matrix), len(matrix[0])
    for i in range(1, m):
      curr_dp = [ord(matrix[i][0]) - 48] + [0] * (n - 1)
      max_len = max(max_len, curr_dp[0])
      for j in range(1, n):
        if matrix[i][j] == "0":
          curr_dp[j] = 0
          continue       
        prev_len = prev_dp[j - 1]
        max_height = max_width = 1
        for k in range(i - 1, i - prev_len - 1, -1):
          if matrix[k][j] == "0": break
          max_height += 1
        for k in range(j - 1, j - prev_len - 1, -1):
          if matrix[i][k] == "0": break
          max_width  += 1
        curr_dp[j] = min(max_height, max_width)
        max_len = max(max_len, curr_dp[j])
      prev_dp = curr_dp
    return max_len ** 2

dp[i][j] 更有效率的計算方式

dp[i][j] = (min(dp[i – 1][j – 1], dp[i – 1][j], dp[i][j – 1]) + 1) if matrix[i][j] == “1” else 0

class Solution:
  def maximalSquare(self, matrix: List[List[str]]) -> int:
    prev_dp = [ord(c) - 48 for c in matrix[0]]
    max_len = max(prev_dp)
    m, n = len(matrix), len(matrix[0])
    for i in range(1, m):
      curr_dp = [ord(matrix[i][0]) - 48] + [0] * (n - 1)
      max_len = max(max_len, curr_dp[0])
      for j in range(1, n):      
        curr_dp[j] = (min(prev_dp[j - 1], 
                          prev_dp[j], 
                          curr_dp[j - 1]) + 1) \
                     if matrix[i][j] == "1" else 0
        max_len = max(max_len, curr_dp[j])
      prev_dp = curr_dp
    return max_len ** 2

Last Updated on 2023/08/16 by A1go