​LeetCode刷题实战132:分割回文串 II

程序IT圈

共 2273字,需浏览 5分钟

 ·

2020-12-26 11:13

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 分割回文串 II,我们先来看题面:
https://leetcode-cn.com/problems/palindrome-partitioning-ii/

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

题意

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回符合要求的最少分割次数。


样例


示例:

输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。


解题

https://blog.csdn.net/zhang_han666/article/details/110524143

思路:动态规划
定义dp[i-1]为子串s[0:i-1](前闭后闭)的最小分割次数,推出dp[i]的转移方程。
  • 首先,如果s[0:i]本身是一个回文串,那么不需要分割,dp[i] = 0

  • 如果s[0:i]不是回文串,那么我们需要枚举以s[i]结尾的回文串,从1i的索引j,判断s[j:i]是不是回文串,如果是,则dp[i]=dp[j-1]+1,即在前j-1个字符串的基础上多一次切割。枚举所有可能的j,取最小值。

  • 不可以逐次判断是否是回文串,会超时,因此回文串的判断也采取动态规划的思想。如果一个字符串s[i:j]是回文串,那么其子串s[i+1:j-1]也是回文串。因此,dp[i][j]表示子串s[i:j]是否是回文串,我们枚举字符串子串的长度,再枚举子串的起始位置,填充dp。


class Solution(object):
    def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """

        l = len(s)
        dpPart = [[False]*l for _ in range(l)]
        dp = [i for i in range(l)]

        # 判断回文串,填充dpPart
        # 枚举子串长度
        for length in range(l):
            # 枚举子串开始位置,length==0表示子串长度为1
            for i in range(l):
                j = i + length
                if j >= l:
                    break
                if length == 0:
                    dpPart[i][j] = True
                elif length == 1:
                    dpPart[i][j] = (s[i] == s[j])
                else:
                    dpPart[i][j] = dpPart[i+1][j-1] and (s[i] == s[j])

        # 填充dp
        for i in range(1, l):
            if dpPart[0][i]:
                dp[i] = 0
                continue

            for j in range(1, i+1):
        # 枚举以s[i]结尾的回文串
                if (dpPart[j][i]):
                    dp[i] = min(dp[i], dp[j - 1] + 1)

        return dp[l - 1]


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力。

上期推文:

LeetCode1-120题汇总,希望对你有点帮助!
LeetCode刷题实战121:买卖股票的最佳时机
LeetCode刷题实战122:买卖股票的最佳时机 II
LeetCode刷题实战123:买卖股票的最佳时机 III
LeetCode刷题实战124:二叉树中的最大路径和
LeetCode刷题实战125:验证回文串
LeetCode刷题实战126:单词接龙 II
LeetCode刷题实战127:单词接龙
LeetCode刷题实战128:最长连续序列
LeetCode刷题实战129:求根到叶子节点数字之和
LeetCode刷题实战130:被围绕的区域
LeetCode刷题实战131:分割回文串


浏览 23
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报