132. 分割回文串 II

🔴   🔖  字符串 动态规划  🔗 力扣 LeetCode

题目

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.

Example 1:

Input: s = "aab"

Output: 1

Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"

Output: 0

Example 3:

Input: s = "ab"

Output: 1

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase English letters only.

题目大意

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

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

示例 1：

输入： s = "aab"

输出： 1

解释： 只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入： s = "a"

输出： 0

示例 3：

输入： s = "ab"

输出： 1

提示：

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

解题思路

1. 状态定义：

   • 用数组 dp[i] 表示从字符串开头到索引 i-1 的最小切割次数。

2. 转移方程：

   • 如果某一段子串 s[left:right] 是回文，那么我们可以尝试在该回文结束处更新 dp[right]：
   • dp[right] = min(dp[right], dp[left] + 1)
   • dp[left] 表示在 left-1 位置的最小切割数，加 1 表示将当前回文子串分割出来。

3. 中心扩展判断回文：

   • 使用中心扩展法，同时寻找奇数长度和偶数长度的回文子串。
   • 对每个中心位置 i：
     • 奇数长度回文：s[i-j] == s[i+j]。
     • 偶数长度回文：s[i-j+1] == s[i+j]。

4. 最终答案：

   • dp[n] 即整个字符串的最小切割次数。

具体算法如下：

1. 初始化 dp 数组，dp[i] 的初始值为 i - 1，表示最坏情况下的切割数（每个字符都单独成为一个回文子串）。
2. 遍历每个字符位置 i 作为中心，分别扩展寻找奇数长度和偶数长度的回文子串。
3. 在扩展过程中，更新 dp 值，记录当前回文子串结束位置的最小切割数。
4. 返回 dp[n]，即整个字符串的最小切割数。

复杂度分析

• 时间复杂度：O(n^2)，中心扩展法需要遍历 n 个字符，并向两侧扩展判断回文，最坏情况下每个字符需要扩展 O(n) 次。
• 空间复杂度：O(n)，动态规划数组 dp 需要 O(n) 空间。

代码

/**
 * @param {string} s
 * @return {number}
 */
var minCut = function (s) {
	const n = s.length;
	// 初始化 dp 数组，dp[i] 表示 s[0:i-1] 的最小切割次数
	let dp = new Array(n + 1).fill().map((_, i) => i - 1);

	// 遍历每个中心位置 i
	for (let i = 0; i < n; i++) {
		// 处理奇数长度回文
		for (let j = 0; i - j >= 0 && i + j < n && s[i - j] === s[i + j]; j++) {
			dp[i + j + 1] = Math.min(dp[i + j + 1], dp[i - j] + 1);
		}

		// 处理偶数长度回文
		for (
			let j = 1;
			i - j + 1 >= 0 && i + j < n && s[i - j + 1] === s[i + j];
			j++
		) {
			dp[i + j + 1] = Math.min(dp[i + j + 1], dp[i - j + 1] + 1);
		}
	}

	// 返回整个字符串的最小切割次数
	return dp[n];
};

相关题目

题号	标题	题解	标签	难度	力扣
131	分割回文串	[✓]	字符串 动态规划 回溯	🟠	🀄️ 🔗
1745	分割回文串 IV		字符串 动态规划	🔴	🀄️ 🔗
2472	不重叠回文子字符串的最大数目		贪心 双指针 字符串 1+	🔴	🀄️ 🔗
2518	好分区的数目		数组 动态规划	🔴	🀄️ 🔗