美文网首页
leetcode132 分割回文串 II golang

leetcode132 分割回文串 II golang

作者: lucasgao | 来源:发表于2021-03-08 22:24 被阅读0次

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
}

相关文章

  • leetcode132 分割回文串 II golang

    132. 分割回文串 II[https://leetcode-cn.com/problems/palindrome...

  • 2021.3.8每日一题

    132. 分割回文串 II[https://leetcode-cn.com/problems/palindrome...

  • 132. 分割回文串 II

    132. 分割回文串 II[https://leetcode-cn.com/problems/palindrome...

  • LeetCode-131-分割回文串

    LeetCode-131-分割回文串 131. 分割回文串[https://leetcode-cn.com/pro...

  • 108. 分割回文串 II

    描述 给定字符串 s, 需要将它分割成一些子串, 使得每个子串都是回文串. 最少需要分割几次? 样例 思路: 考虑...

  • 132. 分割回文串 II

    给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。返回符合要求的 最少分割次数 。输入:s = ...

  • lintcode-分割回文串

    给定一个字符串s,将s分割成一些子串,使每个子串都是回文串。 返回s所有可能的回文串分割方案。

  • 131. 分割回文串

    给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 ...

  • LeetCode-131-分割回文串

    分割回文串 题目描述:给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能...

  • LeetCode 131. 分割回文串

    题目 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。回文...

网友评论

      本文标题:leetcode132 分割回文串 II golang

      本文链接:https://www.haomeiwen.com/subject/abbmqltx.html