[tag] recursive, hashmap/dict,
- use an hash map/ dict for the max area/lenth for each cell
- check right, down and corner to see if it can be a square.
- recursively check the lenth of the adjusent squere and add them to the dict
'''
start from 00
right = max length of left
down = max length
corner = max length
cur_len = 1 + min(right, down, corner)
'''
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
len_dict = {}
ROW, COL= len(matrix), len(matrix[0])
def helper(i, j):
if i >= ROW or j >= COL:
return 0
if (i, j) not in len_dict:
right = helper(i, j+1)
down = helper(i + 1, j)
corner = helper(i+1, j+1)
len_dict[(i,j)] = 0
if matrix[i][j] == '1':
len_dict[(i,j)] = 1 + min(right, down, corner)
return len_dict[(i,j)]
helper(0,0)
return max(len_dict.values())**2