Python DP


  • 0
    class Solution(object):
        def maximalSquare(self, matrix):
            if not matrix:
                return 0
            h, w = len(matrix), len(matrix[0])
            dp = [ [0 for i in xrange(w)] for j in xrange(h) ]
            row, col = 0, [ 0 for i in xrange(w) ]
            ans = 0
            for i in xrange(h):
                row = 0
                for j in xrange(w):
                    if matrix[i][j] == '0':
                        row, col[j] = 0, 0
                        dp[i][j] = 0
                    else:
                        row, col[j] = row + 1, col[j] + 1
                        dp[i][j] = min(row, dp[i - 1][j - 1] + 1, col[j]) if i >= 1 and j >= 1 else 1
                        ans = max(ans, dp[i][j])
            return ans ** 2
    

Log in to reply
 

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