日期: 2025年3月3日

目标

给你一个由小写字母组成的字符串 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 个非空回文子串，允许修改字符中的任意字符，求修改字符的最小次数。

需要将字符串分割成 k 份并且每一份都是回文。我们需要暴力枚举所有可能的分法，并求得每种分法的修改次数，取其最小值。

核心逻辑：

• 计算所有子串变为回文的修改次数，ops[i][j] = s.charAt(i) == s.charAt(j) ? ops[i + 1][j - 1] : ops[i + 1][j - 1] + 1;。由于需要从 i + 1 转移过来，所以外层倒序。初始化数组所有值为 0，外层从倒数第二个开始，内层从 i + 1 开始。
• 从起点 i = 0 开始，枚举所有终点 j，无论 s[i~j] 是否是回文，我们直接加上 ops[i][j]，k-- 接着以 j + 1 为起点继续递归搜索。
• 结束条件：
  • i 未到结尾 k 先减为 0，不符合要求，返回 INF，可以取 0x3f3f3f3f
  • i == s.length()，如果 k == 0 返回 0，否则说明分割的子串没有 k 个，不符合题意返回 INF

代码

/**
 * @date 2025-03-03 8:52
 */
public class PalindromePartition1278 {

    public int palindromePartition(String s, int k) {
        int n = s.length();
        int[][] ops = new int[n][n];
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                ops[i][j] = s.charAt(i) == s.charAt(j) ? ops[i + 1][j - 1] : ops[i + 1][j - 1] + 1;
            }
        }
        int[][] mem = new int[n][k + 1];
        for (int[] row : mem) {
            Arrays.fill(row, -1);
        }
        return dfs(0, k, s, ops, mem);
    }

    public int dfs(int i, int k, String s, int[][] ops, int[][] mem) {
        int n = s.length();
        if (i == n) {
            return k > 0 ? 0x3f3f3f3f : 0;
        }
        if (k == 0) {
            return 0x3f3f3f3f;
        }
        if (mem[i][k] != -1) {
            return mem[i][k];
        }
        int res = Integer.MAX_VALUE;
        for (int j = i; j < n; j++) {
            res = Math.min(res, ops[i][j] + dfs(j + 1, k - 1, s, ops, mem));
        }
        mem[i][k] = res;
        return res;
    }

}

性能