forked from soapyigu/LeetCode-Swift
-
Notifications
You must be signed in to change notification settings - Fork 0
/
MaximalSquare.swift
37 lines (30 loc) · 1.12 KB
/
MaximalSquare.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Question Link: https://leetcode.com/problems/maximal-square/
* Primary idea: Dynamic Programming, new one is equal to the min square width plus one
* Time Complexity: O(mn), Space Complexity: O(mn)
*/
class MaximalSquare {
func maximalSquare(matrix: [[Character]]) -> Int {
guard matrix.count != 0 else {
return 0
}
let m = matrix.count
let n = matrix[0].count
var max_global = 0
var maxSquareSide = Array(count: m, repeatedValue: (Array(count: n, repeatedValue: 0)))
for i in 0 ..< m {
for j in 0 ..< n {
guard matrix[i][j] != "0" else {
continue;
}
if i == 0 || j == 0 {
maxSquareSide[i][j] = 1
} else {
maxSquareSide[i][j] = min(maxSquareSide[i][j - 1], maxSquareSide[i - 1][j], maxSquareSide[i - 1][j - 1]) + 1
}
max_global = max(max_global, maxSquareSide[i][j])
}
}
return max_global * max_global
}
}