Maximal Square

题目描述

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

解题方法

brute force

找出所有的square, 再check是否都是1

DP

这一道题应该通过画图来理解，dp[i][j]表示以[i, j]为右下角时最大square的边长

画图就可以看出，dp[i][j]和dp[i-1], dp[i][j-1]还有dp[i-1][j-1]有关

Solution

我的code

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0
        maxLength = 0

        rowNum = len(matrix)
        colNum = len(matrix[0])


        dp = [[0 for i in range(colNum)] for j in range(rowNum)]

        for i in range(rowNum):
            if matrix[i][0] == "1":
                dp[i][0] = 1
                maxLength = 1

        for j in range(colNum):
            if matrix[0][j] == "1":
                dp[0][j] = 1
                maxLength = 1

        for i in range(1, rowNum):
            for j in range(1, colNum):
                if matrix[i][j] == "0":
                    dp[i][j] = 0
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    maxLength = dp[i][j] if dp[i][j] > maxLength else maxLength

        return maxLength ** 2

别人更简洁的code

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0

        # 学习这种写法
        dp = [[0 for x in row] for row in matrix]

        max_square_size = 0
        # 学习这种2维loop的写法
        for i, row in enumerate(matrix):
            for j, elem in enumerate(row):
                if i == 0 or j == 0:
                    dp[i][j] = 1 if matrix[i][j] == "1" else 0
                else:
                    dp[i][j] =  0 if matrix[i][j] == "0" else min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

                if dp[i][j] > max_square_size:
                    max_square_size = dp[i][j]

        return max_square_size**2

Reference