☆打卡算法☆LeetCode 132. 分割回文串 II 算法解析

恬静的小魔龙 发表于 2022/06/29 11:22:44 2022/06/29
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定一个字符串,将字符串分割成一些子串,使每个子串都是回文串,返回符合要求的最少分割次数。”题目链接:来源:力扣(LeetCod...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

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

题目链接:

来源:力扣(LeetCode)

链接: 132. 分割回文串 II - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1:
输入: s = "aab"
输出: 1
解释: 只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2:
输入: s = "a"
输出: 0

二、解题

1、思路分析

这道题是一道常规的动态规划提,首先定义f[r]为将[1,r]这一段字符分割成若干回文串的最小分割次数,那么答案就是f[n]。

那么就可以考虑f[r]是如何进行转移的:

  • 从起点开始到第r个字符,能形成回文串,最小分割次数为0,此时f[r]=0
  • 从起点开始到第r个字符,不能形成回文串,那么如果[l,r]这一段是回文串的话,那么就有f[r]=f[l-1]+1

枚举左端点,找出所有满足回文要求的左端点,在方案中选最小的一个即可。

2、代码实现

代码参考:

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] g = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(g[i], true);
        }

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                g[i][j] = s.charAt(i) == s.charAt(j) && g[i + 1][j - 1];
            }
        }

        int[] f = new int[n];
        Arrays.fill(f, Integer.MAX_VALUE);
        for (int i = 0; i < n; ++i) {
            if (g[0][i]) {
                f[i] = 0;
            } else {
                for (int j = 0; j < i; ++j) {
                    if (g[j + 1][i]) {
                        f[i] = Math.min(f[i], f[j] + 1);
                    }
                }
            }
        }

        return f[n - 1];
    }
}

image.png

3、时间复杂度

时间复杂度:O(n2)

其中n是字符串s的长度。

空间复杂度:O(n2)

其中n是字符串的长度。

三、总结

由于状态g[l[r]依赖于状态g[l+1][r-1],因此遍历左端点l是从大到小,遍历右端点r是从小到大。

因此最终的遍历过程可以优化为:

  • 右端点r一直往右移动
  • 左端点l在r在左边开始,一直往左移动
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。