# 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
}