<p>Given an <code>m x n</code> binary <code>matrix</code> filled with <code>0</code>&#39;s and <code>1</code>&#39;s, <em>find the largest square containing only</em> <code>1</code>&#39;s <em>and return its area</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg" style="width: 400px; height: 319px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/26/max2grid.jpg" style="width: 165px; height: 165px;" />
<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;,&quot;1&quot;],[&quot;1&quot;,&quot;0&quot;]]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> matrix = [[&quot;0&quot;]]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == matrix.length</code></li>
	<li><code>n == matrix[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>matrix[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        def isSquare(m, n, s):
            # check whether square chould expand from (m+s-1, n+s-1) -> (m+s,n+s)
            # return true or false, and area of the current square
            for i in range(s):
               
                if matrix[m+i][n+s-1] == "0" or matrix[m+s-1][n+i] == "0":
                    
                    return False, (s-1) ** 2
            return True, (s) ** 2

        
        memo = {}
        max_area = 0
        print(len(matrix), len(matrix[0]))
        
        def dp(m, n):
            nonlocal max_area

         

            if m == len(matrix) or n == len(matrix[0]):
                #print(m, n)
                return 0
            if (m,n) in memo:
                return memo[(m,n)]
            #print("check 0","row = ", m, "col = ",n, "element = ", matrix[m][n])

            if matrix[m][n] == "0":
                #print("check 1","row = ", m, "col = ",n, matrix[m][n])

                ans = max(dp(m+1,n), dp(m,n+1))
            
            else:
                s = 1
                curr_area = 1
                
                while m + s - 1  < len(matrix) and n+s-1 < len(matrix[0]):
                    #print("check 2","row = ", m, "col = ",n, matrix[m][n], "area =",curr_area)
                    flag, curr_area = isSquare(m, n, s)
                    if not flag:
                        break
                    s += 1
                
  
                max_area = max(max_area, curr_area)
                #print("max_area =", max_area)
                if curr_area == (len(matrix)-1)**2:
                    #print("check 3")
                    ans = 0


                else:
                    #print("check 4")
                    ans = max(dp(m, n + 1), dp(m + 1, n))
                
            memo[(m,n)] = ans
            
            return ans

        dp(0, 0)
        
        return max_area
            
                
                
            
        
        
38825