Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4
My code:
class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
length=len(matrix)
if length==0:
return 0
example=matrix[0]
len2=len(example)
if len2==0:
return 0
self.record=[[-1]*len2 for _ in range(length)]
self.max_value=0
if len2==1 or length==1:
for i in range(length):
for j in range(len2):
if matrix[i][j]=='1':
return 1
return 0
self.check_Result(matrix,length-1,len2-1)
print(self.record)
return int(self.max_value)**2
def check_Result(self,matrix,i,j):
if i==0 or j==0:
self.max_value=max(self.max_value,int(matrix[i][j]))
return int(matrix[i][j])
if i<0 or j<0:
return 0
if self.record[i][j]!=-1:
return self.record[i][j]
result1=self.check_Result(matrix,i-1,j-1)
result2=self.check_Result(matrix,i,j-1)
result3=self.check_Result(matrix,i-1,j)
#print(result1)
#print(result2)
#print(result3)
#print(i)
#print(j)
min_value=min(result1,result2,result3)
if matrix[i][j]=='1':
self.record[i][j]=min_value+1
self.max_value=max(self.max_value,self.record[i][j])
else:
self.record[i][j]=0
return self.record[i][j]