221. Maximal Square (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        m, n = len(matrix), len(matrix[0])    
        dp = [0] * (n + 1)
        result = prev = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "1":
                    dp[j + 1], prev = min(prev, dp[j + 1], dp[j]) + 1, dp[j + 1]
                    result = max(result, dp[j + 1])
                else:
                    dp[j + 1] = 0
        return result ** 2