132. 分割回文串 II
链接
作者：Ethan3014
题目.
难度:high
解答：dp用来表示前n个字符串最小需要多少次cut。另外先计算好各个子字符串是否是回文.之前想到过一个dp[i][j]表示是s[i:j+1]最少需要多少次切割。这个思路是对的，但是复杂度变为n**3了，没有利用到最后一次右边的字符串一定是回文的特性。
package main
import "fmt"
func minCut(s string) int {
if len(s) <= 1 {
return 0
}
palis := make([][]bool, len(s))
for i := 0; i < len(s); i++ {
palis[i] = make([]bool, len(s))
}
for j := 0; j = 0; i-- {
if s[i] == s[j] && (j-i < 3 || palis[i+1][j-1]) {
palis[i][j] = true
}
}
}
if palis[0][len(s)-1] {
return 0
}
dp := make([]int, len(s))
dp[0] = 0
for j := 1; j 0; i-- {
if palis[i][j] && (dp[i-1]+1) < dp[j] {
dp[j] = dp[i-1] + 1
}
}
}
return dp[len(s)-1]
}
func main() {
fmt.Println(minCut("cdd"))
}
复杂度分析
time
O(n*n)
spaceO(n*n)
执行结果执行用时 :
8 ms
, 在所有 Go 提交中击败了
60.87%
的用户
内存消耗 :
5.1 MB
, 在所有 Go 提交中击败了
68.97%
的用户
作者：Ethan3014
