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

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，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];
    }
}

3、时间复杂度

时间复杂度：O(n²)

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

空间复杂度：O(n²)

其中n是字符串的长度。

三、总结

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

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

• 右端点r一直往右移动
• 左端点l在r在左边开始，一直往左移动