Space can be optimized as we don't need to keep the whole dp grid as we progress down the rows in matrix
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
m = len(matrix)
n = len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_len = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
# 有些tricky
dp[i+1][j+1] = min(dp[i][j], dp[i+1][j], dp[i][j+1]) + 1
if dp[i+1][j+1] > max_len:
max_len = dp[i+1][j+1]
return max_len * max_len