[LeetCode] 每日一题 1278. 分割回文串 III

题目链接

https://leetcode.cn/problems/palindrome-partitioning-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 个回文子串，并求出最少修改多少个字符，使得所有子串都是回文串。这道题比昨天的题目难度更大，仍然可以采用动态规划来解决，分为两步：

1. 预处理回文转换代价：
   先计算 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（需要修改一次）

2. 动态规划求最优分割方案：
   设 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 在字符串处理中的应用

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。