maximal_square

hitzzc · hitzzc · commit cc1d44e1a562 · 2016-10-17T16:41:22.000+08:00
diff --git a/README.md b/README.md
@@ -177,6 +177,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [217. Contains Duplicate](https://github.com/hitzzc/go-leetcode/tree/master/contains_duplicate)
 #### [218. Contains Duplicate II](https://github.com/hitzzc/go-leetcode/tree/master/contains_duplicate_II)
 #### [219. Contains Duplicate III (unsolved)](https://github.com/hitzzc/go-leetcode/tree/master/contains_duplicate_III)
+#### [221. Maximal Square](https://github.com/hitzzc/go-leetcode/tree/master/maximal_square)
 
 
 
diff --git a/maximal_square/maximal_square.go b/maximal_square/maximal_square.go
@@ -0,0 +1,36 @@
+package maximal_square
+
+func maximalSquare(matrix [][]byte) int {
+	if len(matrix) == 0 || len(matrix[0]) == 0 {
+		return 0
+	}
+	m := map[byte]int{
+		'0': 0,
+		'1': 1,
+	}
+	p := make([][]int, len(matrix))
+	for i := range p {
+		p[i] = make([]int, len(matrix[i]))
+	}
+	max := 0
+	for i := range matrix {
+		for j := range matrix[i] {
+			if i == 0 || j == 0 {
+				p[i][j] = m[matrix[i][j]]
+			} else if matrix[i][j] == '1' {
+				p[i][j] = min(min(p[i-1][j], p[i][j-1]), p[i-1][j-1]) + 1
+			}
+			if p[i][j] > max {
+				max = p[i][j]
+			}
+		}
+	}
+	return max * max
+}
+
+func min(i, j int) int {
+	if i < j {
+		return i
+	}
+	return j
+}
