leetcode132 分割回文串 II golang
作者:
lucasgao | 来源:发表于
2021-03-08 22:24 被阅读0次
![](https://img.haomeiwen.com/i5899140/6de400f15725e6d1.png)
image.png
解题思路
- 首先预计算
dp[i][j]
用来表示 s[i:j+1]
是否为回文字符串
- 其中
dp[i][j]= s[i]==s[j] && dp[i+1][j-1]
- 然后再设
A[i]
表示为 s[0:i+1] 需要切割的次数
- 则有转移方程
A[i]= A[j]+1
, 其中 j<i
并且 s[j+1:i]
为回文字符串
- 如果s[:i+1]本身为回文字符串,则
A[i]=0
,不需要再遍历j
代码
func minCut(s string) int {
if len(s)==1{
return 0
}
n := len(s)
dp := make([][]bool,n)
for i:=range dp{
dp[i]=make([]bool,n)
dp[i][i]=true
if i>0{
dp[i][i-1]=true
}
}
for l:=2;l<=n;l++{
for i:=0;i+l<=n;i++{
j := i+l-1
dp[i][j] = s[i]==s[j] && dp[i+1][j-1]
}
}
A := make([]int,n)
A[0]=0
for i:=1;i<n;i++{
if dp[0][i]{
continue
}
A[i]=1e9
for j:=0;j<i;j++{
if dp[j+1][i]{
A[i]=min(A[i],A[j]+1)
}
}
}
// fmt.Println(A)
return A[len(A)-1]
}
func min(a,b int)int{
if a<b{
return a
}
return b
}
本文标题:leetcode132 分割回文串 II golang
本文链接:https://www.haomeiwen.com/subject/abbmqltx.html
网友评论