[LeetCode] 每日一题 1278. 分割回文串 III
题目链接
题目描述
给你一个由小写字母组成的字符串 s
,和一个整数 k
。
请你按下面的要求分割字符串:
首先,你可以将
s
中的部分字符修改为其他的小写英文字母。接着,你需要把
s
分割成k
个非空且不相交的子串,并且每个子串都是回文串。
请返回以这种方式分割字符串所需修改的最少字符数。
示例输入
示例 1
输入:s = "abc", k = 2
输出:1
解释:你可以把字符串分割成 "ab" 和 "c",并修改 "ab" 中的 1 个字符,将它变成回文串。
示例 2
输入:s = "aabbc", k = 3
输出:0
解释:你可以把字符串分割成 "aa"、"bb" 和 "c",它们都是回文串。
示例 3
输入:s = "leetcode", k = 8
输出:0
提示
1 <= k <= s.length <= 100
s
中只含有小写英文字母。
解题思路
本题要求将字符串 s
分割成 k
个回文子串,并求出最少修改多少个字符,使得所有子串都是回文串。这道题比昨天的题目难度更大,仍然可以采用动态规划来解决,分为两步:
预处理回文转换代价:
先计算cost[i][j]
,表示将s[i:j]
修改为回文串所需的最小修改次数。其计算方式是:如果
s[i] == s[j]
,那么cost[i][j] = cost[i+1][j-1]
(无需额外修改)如果
s[i] != s[j]
,那么cost[i][j] = cost[i+1][j-1] + 1
(需要修改一次)
动态规划求最优分割方案:
设dp[i][j]
表示前i
个字符分割成j
个回文子串的最小修改次数:dp[i][1] = cost[0][i-1]
,即s[0:i-1]
作为一个整体变成回文串的代价dp[i][j] = min(dp[x][j-1] + cost[x][i-1])
,遍历x
作为j-1
段的结尾,然后s[x:i-1]
作为新的回文段,求最小修改次数
最终返回 dp[n][k]
,即 s[0:n]
被分割成 k
个回文子串的最小修改次数
代码实现
class Solution {
public int palindromePartition(String s, int k) {
int n = s.length();
int[][] cost = new int[n][n];
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
cost[i][j] = cost[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
}
}
int[][] dp = new int[n + 1][k + 1];
for (int[] a : dp) {
Arrays.fill(a, Integer.MAX_VALUE);
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= Math.min(k, i); j++) {
if (j == 1) {
dp[i][j] = cost[0][i - 1];
} else {
for (int x = j - 1; x < i; x++) {
dp[i][j] = Math.min(dp[i][j], dp[x][j - 1] + cost[x][i - 1]);
}
}
}
}
return dp[n][k];
}
}
复杂度分析
时间复杂度:
预处理
cost[i][j]
需要 O(n^2) 时间动态规划
dp[i][j]
的计算也需要 O(n^2) 的复杂度(遍历x
计算dp[i][j]
)因此,总体时间复杂度为 O(n^2 + n^2) = O(n^2)
空间复杂度:
cost
数组占用 O(n^2) 空间dp
数组占用 O(nk) 空间总体空间复杂度为 O(n^2 + nk) ≈ O(n^2)
总结
本题采用动态规划求解,先预处理回文转换代价,然后利用 DP 计算最小修改次数。相比昨天的题目,这道题增加了字符串修改的部分,使得 DP 状态转移更加复杂。通过这道题,我进一步掌握了 DP 在字符串处理中的应用
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。