Leetcode 221. Maximal Square

Seawolf

1. Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
   
2. 
   
3. Example:
   
4. 
   
5. Input:
   
6. 
   
7. 1 0 1 0 0
   
8. 1 0 1 1 1
   
9. 1 1 1 1 1
   
10. 1 0 0 1 0
    
11. 
    
12. Output: 4

复制代码

n³ method using 2d matrix presum

1. class Solution:
   
2.     def maximalSquare(self, matrix: List[List[str]]) -> int:
   
3.         if matrix == None or len(matrix) == 0 or len(matrix[0]) == 0:
   
4.             return 0
   
5.         sum_val = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)]
   
6.         
   
7.         for i in range(1, len(sum_val)):
   
8.             for j in range(1, len(sum_val[0])):
   
9.                 sum_val[i][j] = sum_val[i - 1][j] + sum_val[i][j - 1] - sum_val[i - 1][j - 1] + int(matrix[i - 1][j - 1])
   
10.         
    
11.         m = len(matrix)
    
12.         n = len(matrix[0])
    
13.         result = 0
    
14.         
    
15.         for i in range(1, m + 1):
    
16.             for j in range(1, n + 1):
    
17.                 for size in range(1, min(m - i + 1, n - j + 1) + 1):
    
18.                     if sum_val[i + size - 1][j + size - 1] - sum_val[i - 1][j + size - 1] - sum_val[i + size - 1][j - 1] + sum_val[i - 1][j - 1] == (size) * (size):
    
19.                         result = max(result, (size) * (size))
    
20.         
    
21.         return result

复制代码

n² method using dynamic programming

1. class Solution:
   
2.     def maximalSquare(self, matrix: List[List[str]]) -> int:
   
3.         if matrix == None or len(matrix) == 0 or len(matrix[0]) == 0:
   
4.             return 0
   
5.         size = [[0 for _ in range(len(matrix[0]) + 1)] for _ in range(len(matrix) + 1)]
   
6.         result = 0
   
7.         for i in range(1, len(matrix) + 1):
   
8.             for j in range(1, len(matrix[0]) + 1):
   
9.                 if matrix[i - 1][j - 1] == '1':
   
10.                     size[i][j] = min(size[i - 1][j], size[i][j - 1], size[i - 1][j - 1]) + 1
    
11.                     result = max(result, size[i][j])
    
12.         return result * result

复制代码