Alibi

My Life is Getting Better

Leetcode[221]Maximal Square

21 Nov 2015

###Task1 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.

###Python ####O(n)

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0
        M = len(matrix)
        N = len(matrix[0])
        dp = [[0 for i in range(N)] for j in range(M)]
        for i in range(M):
            dp[i][0] = ord(matrix[i][0]) - ord('0')
        for j in range(N):
            dp[0][j] = ord(matrix[0][j]) - ord('0')
        for i in range(1, M):
            for j in range(1, N):
                if matrix[i][j] == '1':
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
        ret = 0
        for i in range(M):
            for j in range(N):
                ret = max(ret, dp[i][j] * dp[i][j])
        return ret

###Java

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] sq = new int[row][col]; // sq[x][y] stands for the length of squar formed before node x, y
        for (int i = 0; i < row; i++) {
            sq[i][0] = matrix[i][0] - '0';
        }
        for (int i = 0; i < col; i++) {
            sq[0][i] = matrix[0][i] - '0';
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == '1') {
                    sq[i][j] = Math.min(sq[i - 1][j], Math.min(sq[i][j - 1], sq[i - 1][j - 1])) + 1;
                }
            }
        }
        int maxSq = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                maxSq = Math.max(maxSq, sq[i][j] * sq[i][j]);
            }
        }
        
        return maxSq;
    }
}

###Points

动态规划（Dynamic Programming） 状态转移方程： dp[x][y] = min(dp[x - 1][y - 1], dp[x][y - 1], dp[x - 1][y]) + 1 上式中，dp[x][y]表示以坐标(x, y)为右下角元素的全1正方形矩阵的最大长度（宽度）

Related Posts