leetcode132 分割回文串 II golang

132. 分割回文串 II

image.png

解题思路

1. 首先预计算 dp[i][j] 用来表示 s[i:j+1]是否为回文字符串
   1. 其中 dp[i][j]= s[i]==s[j] && dp[i+1][j-1]
2. 然后再设 A[i] 表示为 s[0:i+1] 需要切割的次数
   1. 则有转移方程 A[i]= A[j]+1, 其中 j<i 并且 s[j+1:i]为回文字符串
   2. 如果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
}

有疑问加站长微信联系（非本文作者）