1278-分割回文串 III(Palindrome Partitioning III)

原文链接: https://leetcode-cn.com/problems/palindrome-partitioning-iii

英文原文

You are given a string s containing lowercase letters and an integer k. You need to :

First, change some characters of s to other lowercase English letters.
Then divide s into k non-empty disjoint substrings such that each substring is a palindrome.

Return the minimal number of characters that you need to change to divide the string.

Example 1:

Input: s = "abc", k = 2
Output: 1
Explanation: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

Example 2:

Input: s = "aabbc", k = 3
Output: 0
Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3:

Input: s = "leetcode", k = 8
Output: 0

Constraints:

1 <= k <= s.length <= 100.
s only contains lowercase English letters.

中文题目

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

通过代码

高赞题解

方法一：动态规划

我们用 f[i][j] 表示对于字符串 S 的前 i 个字符，将它分割成 j 个非空且不相交的回文串，最少需要修改的字符数。在进行状态转移时，我们可以枚举第 j 个回文串的起始位置 i0，那么就有如下的状态转移方程：

f[i][j] = min(f[i0][j - 1] + cost(S, i0 + 1, i))

其中 cost(S, l, r) 表示将 S 的第 l 个到第 r 个字符组成的子串变成回文串，最少需要修改的字符数。cost(S, l, r) 可以通过双指针的方法求出：

初始时将第一个指针置于位置 l，第二个指针置于位置 r；
每次比较时，判断两个指针指向的字符是否相等。若相等，则这两个位置构成回文，不需要进行修改；若不相等，则为了保证回文，需要修改其中的任意一个字符；
在每次比较后，将第一个指针向右移动一步，第二个指针向左移动一步，如果第一个指针仍然在第二个指针的右侧，那么继续进行下一次比较。

上述的状态转移方程中有一些边界情况需要考虑，例如只有当 i >= j 时，f[i][j] 的值才有意义，这是因为 i 个字符最多只能被分割成 i 个非空且不相交的字符串，因此在状态转移时，必须要满足 i >= j 且 i0 >= j - 1。此外，当 j = 1 时，我们并不需要枚举 i0，这是因为将前 i 个字符分割成 j = 1 个非空字符串的方法是唯一的。

[sol1]
class Solution {
public:
    int cost(string& s, int l, int r) {
        int ret = 0;
        for (int i = l, j = r; i < j; ++i, --j) {
            if (s[i] != s[j]) {
                ++ret;
            }
        }
        return ret;
    }

    int palindromePartition(string& s, int k) {
        int n = s.size();
        vector<vector<int>> f(n + 1, vector<int>(k + 1, INT_MAX));
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= min(k, i); ++j) {
                if (j == 1) {
                    f[i][j] = cost(s, 0, i - 1);
                }
                else {
                    for (int i0 = j - 1; i0 < i; ++i0) {
                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost(s, i0, i - 1));
                    }
                }
            }
        }
        
        return f[n][k];
    }
};

[sol1]
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def cost(l, r):
            ret, i, j = 0, l, r
            while i < j:
                ret += (0 if s[i] == s[j] else 1)
                i += 1
                j -= 1
            return ret
        
        n = len(s)
        f = [[10**9] * (k + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, min(k, i) + 1):
                if j == 1:
                    f[i][j] = cost(0, i - 1)
                else:
                    for i0 in range(j - 1, i):
                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost(i0, i - 1))
        
        return f[n][k]

复杂度分析

时间复杂度：$O(N^3K)$，其中 $N$ 是字符串 S 的长度。在动态规划中，我们需要枚举 i，j 以及 i0，它们需要的时间分别为 $O(N)$，$O(K)$ 和 $O(N)$。我们还需要计算 cost() 函数来进行状态转移，单次的时间复杂度为 $O(N)$，因此总的时间复杂度为 $O(N^3K)$。在 Python 中，该方法可以卡着时间通过。
空间复杂度：$O(NK)$。

方法二：动态规划 + 预处理

方法一中的时间复杂度瓶颈在于 cost() 函数。在调用 cost() 函数之前，我们枚举了 i，j 以及 i0 ，因此它一共被调用了 $O(N^2K)$ 次。然而观察 cost() 函数本身的形式 cost(S, l, r)，不同的 (l, r) 的数量只有 $O(N^2)$ 种，这说明在动态规划中，我们对 cost() 函数进行了大量的重复调用。因此我们可以预处理出所有的 cost(S, l, r)，在后续调用 cost() 函数时，我们只需要 $O(1)$ 的时间便可以返回结果。

我们同样可以使用动态规划求出所有的 cost(S, l, r)。记 cost[l][r] = cost(S, l, r)，根据方法一中计算 cost() 函数的双指针方法，我们可以得到如下的状态转移方程：

cost[l][r] = cost[l + 1][r - 1],       if S[l] == S[r]
cost[l][r] = cost[l + 1][r - 1] + 1,   if S[l] != S[r]
cost[l][r] = 0,                        if l >= r

这是一个经典的区间动态规划，时间复杂度为 $O(N^2)$。在预处理出所有的 cost(S, l, r) 后，下一步使用动态规划计算 f[i][j] 的时间复杂度就从 $O(N^3K)$ 降低至 $O(N^2K)$。

[sol2]
class Solution {
public:
    int palindromePartition(string& s, int k) {
        int n = s.size();
        vector<vector<int>> cost(n, vector<int>(n));
        for (int span = 2; span <= n; ++span) {
            for (int i = 0; i <= n - span; ++i) {
                int j = i + span - 1;
                cost[i][j] = cost[i + 1][j - 1] + (s[i] == s[j] ? 0 : 1);
            }
        }

        vector<vector<int>> f(n + 1, vector<int>(k + 1, INT_MAX));
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= min(k, i); ++j) {
                if (j == 1) {
                    f[i][j] = cost[0][i - 1];
                }
                else {
                    for (int i0 = j - 1; i0 < i; ++i0) {
                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost[i0][i - 1]);
                    }
                }
            }
        }
        
        return f[n][k];
    }
};

[sol2]
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        cost = [[0] * n for _ in range(n)]
        for span in range(2, n + 1):
            for i in range(n - span + 1):
                j = i + span - 1
                cost[i][j] = cost[i + 1][j - 1] + (0 if s[i] == s[j] else 1)

        f = [[10**9] * (k + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, min(k, i) + 1):
                if j == 1:
                    f[i][j] = cost[0][i - 1]
                else:
                    for i0 in range(j - 1, i):
                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost[i0][i - 1])
        
        return f[n][k]

复杂度分析

时间复杂度：$O(N^2K)$，其中 $N$ 是字符串 S 的长度。预处理 cost() 函数需要的时间为 $O(N^2)$。在动态规划中，我们需要枚举 i，j 以及 i0，它们需要的时间分别为 $O(N)$，$O(K)$ 和 $O(N)$，整体复杂度为 $O(N^2K)$。由于 $O(N^2) < O(N^2K)$，因此算法的总时间复杂度为 $O(N^2K)$。
空间复杂度：$O(N^2 + NK)$。存储 cost() 函数需要的空间为 $O(N^2)$，存储动态规划的结果 f 需要的空间为 $O(NK)$。

统计信息

通过次数	提交次数	AC比率
3812	6324	60.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途