Python 9-Line DP Solution


  • 0
    D
    class Solution(object):
        def maximalSquare(self, matrix):
            """
            :type matrix: List[List[str]]
            :rtype: int
            """
            matrix = [[int(x) for x in y] for y in matrix]
            if not matrix or not matrix[0]: return 0
            m, n = len(matrix), len(matrix[0])
            for i in range(m-2, -1, -1):
                for j in range(n-2, -1, -1):
                    if matrix[i][j] == 0: continue
                    min_size = min(matrix[i][j+1], matrix[i+1][j], matrix[i+1][j+1])
                    if min_size>0 : matrix[i][j] = 1+min_size
            return max(max(x) for x in matrix)**2

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.