221. Maximal Square

Medium

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output:
 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output:
 1

Example 3:

Input: matrix = [["0"]]
Output:
 0

Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 300

• matrix[i][j] is '0' or '1'.

解題

func maximalSquare(matrix [][]byte) int {
    side := 0

    dp := make([][]int, 0)
    for i := 0 ; i < len(matrix); i++ {
        dp = append(dp, make([]int, len(matrix[0])))
    }

    for i := 0 ; i < len(matrix); i++ {
        dp[i][0] = int(matrix[i][0] - '0')
        if dp[i][0] > side {
            side = dp[i][0]
        }
    }

    for i := 0 ; i < len(matrix[0]); i++ {
        dp[0][i] = int(matrix[0][i] - '0')
        if dp[0][i] > side {
            side = dp[0][i]
        }
    }

    for i:=1; i<len(matrix); i++ {
        for j:=1; j<len(matrix[0]); j++ {
            if matrix[i][j] == '0' {
                dp[i][j] = 0
            } else {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1
            }

            if dp[i][j] > side {
                side = dp[i][j]
            }
        }
    }    

    return side * side
}

func min(a, b int) int {
    if a < b { return a }
    return b
}