Create L132.go

ganeshskudva · web-flow · commit 8e79f35459ed · 2021-08-07T15:47:08.000-07:00
diff --git a/Hard/L132.go b/Hard/L132.go
@@ -0,0 +1,28 @@
+package Hard
+
+func minCut(s string) int {
+	cut, n := make([]int, len(s)), len(s)
+	pal := make([][]bool, n*n)
+	for i := 0; i < n; i++ {
+		pal[i] = make([]bool, n)
+	}
+
+	for i := 0; i < n; i++ {
+		min := i
+		for j := 0; j <= i; j++ {
+			if s[j] == s[i] && (j+1 > i-1 || pal[j+1][i-1]) {
+				pal[j][i] = true
+				if j == 0 {
+					min = 0
+				} else {
+					if cut[j-1]+1 < min {
+						min = cut[j-1] + 1
+					}
+				}
+			}
+		}
+		cut[i] = min
+	}
+
+	return cut[n-1]
+}
