"""
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
"""
class Solution1(object):
def maximalSquare(self, matrix):
"""
we use dp[i][j] to denote the side length of a square whose lower right corner is matrix[i][j]
dp[i][j] depend on the min length of dp[i-1][j], dp[i][j-1] and dp[i-1][j-1], their min length + 1 was the side length of new square
"""
if len(matrix) == 0 :return 0
result = 0
dp = [[0]*(len(matrix[0])+1) for _ in range(len(matrix) + 1)]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
dp[i+1][j+1] = (min([dp[i][j], dp[i+1][j], dp[i][j+1]]) + 1 )* int(matrix[i][j])
result = max(result, dp[i+1][j+1])
return result**2
class Solution2(object):
"""
TLE solution
check every point of max square can generate from this point
"""
def maximalSquare(self, matrix):
result = 0
row, col = len(matrix), len(matrix[0])
for i in range(len(matrix)):
for j in range(len(matrix[0])):
result = max(result, self.getMaxSquare(i, j, row, col, matrix))
return result
def getMaxSquare(self, x, y, row, col,matrix):
max_length = min(row - x, col - y)
for length in range(max_length, -1, -1):
count = 0
for i in range(x, x+length):
for j in range(y, y+length):
count += int(matrix[i][j])
if count == length **2: return count
return 0
