“给定一个字符串,将字符串分割成一些子串,使每个子串都是回文串,返回符合要求的最少分割次数。”
题目链接:
来源:力扣(LeetCode)
链接: 132. 分割回文串 II - 力扣(LeetCode) (leetcode-cn.com)
给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1:
输入: s = "aab"
输出: 1
解释: 只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2:
输入: s = "a"
输出: 0
这道题是一道常规的动态规划提,首先定义f[r]为将[1,r]这一段字符分割成若干回文串的最小分割次数,那么答案就是f[n]。
那么就可以考虑f[r]是如何进行转移的:
枚举左端点,找出所有满足回文要求的左端点,在方案中选最小的一个即可。
代码参考:
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];
}
}
时间复杂度:O(n2)
其中n是字符串s的长度。
空间复杂度:O(n2)
其中n是字符串的长度。
由于状态g[l[r]依赖于状态g[l+1][r-1],因此遍历左端点l是从大到小,遍历右端点r是从小到大。
因此最终的遍历过程可以优化为: