palindrome_partitioning_II.go

package palindrome_partitioning_II

funcminCut(sstring) int {
iflen(s) <2 {
return0
 }
matrix:=make([][]bool, len(s))
fori:=rangematrix {
matrix[i] =make([]bool, len(s))
 }
bytes:= []byte(s)
fori:=0; i<len(bytes); i++ {
forj:=0; j<=i; j++ {
ifi==j||bytes[j] ==bytes[i] && (i==j+1||matrix[j+1][i-1]) {
matrix[j][i] =true
 }
 }
 }

records:=make([]int, len(bytes))
fori:=1; i<len(bytes); i++ {
min:=records[i-1] +1
forj:=i-1; j>=0; j-- {
ifmatrix[j][i] {
ifj==0 {
min=0
 } else {
record:=records[j-1] +1
ifrecord<min {
min=record
 }
 }
 }
 }
records[i] =min
 }
returnrecords[len(bytes)-1]
}

funcisPartition(bytes []byte, i, jint) bool {
for ; i<j; i, j=i+1, j-1 {
ifbytes[i] !=bytes[j] {
returnfalse
 }
 }
returntrue
}