Hard

题目描述

给你一个由小写字母组成的字符串 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 仅含小写英文字母。

提示：

  • 对于每个子串，计算使其变为回文串的最少修改次数，并存储在表中。
  • 创建 dp(pos, cnt)，表示从位置 pos 开始的后缀字符串分割成 cnt 个回文串所需的最少修改次数。

解题思路

这是一个经典的动态规划问题，需要分两步解决：

第一步：预计算每个子串变为回文串的最少修改次数 对于字符串的任意区间 [i, j]，我们需要知道将其变为回文串的最少修改次数。使用双指针从两端向中间遍历，当两端字符不同时需要修改一个字符。时间复杂度 O(n²)。

第二步：动态规划求解最优分割方案 定义 dp[i][j] 表示将字符串前 i 个字符分割成 j 个回文串所需的最少修改次数。

状态转移方程：

dp[i][j] = min(dp[t][j-1] + cost[t][i-1]) for all valid t

其中 cost[l][r] 表示将区间 [l, r] 变为回文串的最少修改次数。

边界条件：

  • dp[0][0] = 0（空字符串分成0个回文串）
  • 当 j > i 时，dp[i][j] = ∞（不可能）

优化思路： 由于约束较小（n ≤ 100），直接的 O(n³) 动态规划解法完全可行。也可以考虑记忆化搜索的实现方式。

最终答案为 dp[n][k]，表示将整个字符串分割成 k 个回文串的最少修改次数。

代码实现

class Solution {
public:
    int palindromePartition(string s, int k) {
        int n = s.length();
        
        // 预计算每个区间变为回文串的最少修改次数
        vector<vector<int>> cost(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int l = i, r = j;
                while (l < r) {
                    if (s[l] != s[r]) {
                        cost[i][j]++;
                    }
                    l++;
                    r--;
                }
            }
        }
        
        // dp[i][j] 表示前i个字符分成j个回文串的最少修改次数
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));
        dp[0][0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= min(i, k); j++) {
                for (int t = j - 1; t < i; t++) {
                    if (dp[t][j-1] != INT_MAX) {
                        dp[i][j] = min(dp[i][j], dp[t][j-1] + cost[t][i-1]);
                    }
                }
            }
        }
        
        return dp[n][k];
    }
};

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        
        # 预计算每个区间变为回文串的最少修改次数
        cost = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i, n):
                l, r = i, j
                while l < r:
                    if s[l] != s[r]:
                        cost[i][j] += 1
                    l += 1
                    r -= 1
        
        # dp[i][j] 表示前i个字符分成j个回文串的最少修改次数
        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        
        for i in range(1, n + 1):
            for j in range(1, min(i, k) + 1):
                for t in range(j - 1, i):
                    if dp[t][j-1] != float('inf'):
                        dp[i][j] = min(dp[i][j], dp[t][j-1] + cost[t][i-1])
        
        return dp[n][k]

public class Solution {
    public int PalindromePartition(string s, int k) {
        int n = s.Length;
        
        // 预计算每个区间变为回文串的最少修改次数
        int[,] cost = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int l = i, r = j;
                while (l < r) {
                    if (s[l] != s[r]) {
                        cost[i, j]++;
                    }
                    l++;
                    r--;
                }
            }
        }
        
        // dp[i,j] 表示前i个字符分成j个回文串的最少修改次数
        int[,] dp = new int[n + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.Min(i, k); j++) {
                for (int t = j - 1; t < i; t++) {
                    if (dp[t, j-1] != int.MaxValue) {
                        dp[i, j] = Math.Min(dp[i, j], dp[t, j-1] + cost[t, i-1]);
                    }
                }
            }
        }
        
        return dp[n, k];
    }
}

var palindromePartition = function(s, k) {
    const n = s.length;
    
    // 预计算每个区间变为回文串的最少修改次数
    const cost = Array(n).fill().map(() => Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            let l = i, r = j;
            while (l < r) {
                if (s[l] !== s[r]) {
                    cost[i][j]++;
                }
                l++;
                r--;
            }
        }
    }
    
    // dp[i][j] 表示前i个字符分成j个回文串的最少修改次数
    const dp = Array(n + 1).fill().map(() => Array(k + 1).fill(Infinity));
    dp[0][0] = 0;
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= Math.min(i, k); j++) {
            for (let t = j - 1; t < i; t++) {
                if (dp[t][j-1] !== Infinity) {
                    dp[i][j] = Math.min(dp[i][j], dp[t][j-1] + cost[t][i-1]);
                }
            }
        }
    }
    
    return dp[n][k];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n² + n²k) = O(n²k)
空间复杂度O(n² + nk) = O(n²)

其中 n 为字符串长度，k 为分割数量。时间复杂度主要来自预计算回文串修改次数的 O(n²) 和动态规划的 O(n²k)。空间复杂度主要来自存储预计算结果的二维数组。

相关题目