文章

[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 在字符串处理中的应用

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

License:  CC BY 4.0