❓ 132. 分割回文串 II

难度：困难

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

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

示例 1：

输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。

示例 2：

输入：s = “a”
输出：0

示例 3：

输入：s = “ab”
输出：1

提示：

• $1<=s.length<=2000$
• s 仅由小写英文字母组成

💡思路：动态规划

• 先使用中心扩展法，计算以每个字符为中心的最长回文串，注意
  • 既可以 以单个字符为中心，此时的回文串长度为奇数个；
  • 也可以 以两个相同的字符为中心，此时的回文串为偶数个；
• 在计算每个最长回文串的长度后，得到每个回文串的起始位置，并不断更新以该位置为起点的最长回文串的长度；

🍁代码：(C++、Java)

C++

Java

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：$O(n)$，其中 n 为数组的长度。
• 空间复杂度：$O(n)$，其中 n 为数组的长度。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我LeetCode主页 / CSDN—力扣专栏，每日更新！

注： 如有不足，欢迎指正！