[LeetCode] 1278. Palindrome Partitioning III #1278

grandyang · 2019-05-30T16:34:01Z

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.

这道题是拆分回文串系列的第三道，之前的两道分别是 Palindrome Partitioning II 和 Palindrome Partitioning，相对于前两道题来说，这道题更加的复杂一些，这里给了一个只有小写字母的字符串s和一个正整数k，说是首先改变s中的一些字母，然后将s分割为k个回文串，问最少需要改变多少个字母。再来分析一下题目中给的例子，比如例子1，可以先将字符串 abc 分割成 aac 或者 bbc，然后再分割成两个回文串。例子2给的 aabbc 可以直接分割成三个回文串，并不需要改变字母。例子3正好有八个字母，可以直接拆分为8个回文串，从而并不需要改变字母。所以这道题实际上就是两个部分，如何确定要修改哪些字母，和如何拆分为k个回文串。这两个部分实际上是相辅相成的，假如先不考虑修改字母，而是将字符串s分割成任意的k个子串，然后计算将每个子串变为回文串需要改变的字母个数，全部加起来就是一个解（但不一定是最优解），只有计算出所有的分割的方式，找到其中的最小值，才是本题需要的解。当将字符串分割成k个子串时，需要知道每个子串变为回文串的字母改变个数，由于分割成的子串可能之前也出现过，所以每次都计算一遍如何变为子串，就非常的不高效，可能存在重复计算，最好是能提前计算出每个子串变成回文串的 cost，这样之后需要哪个就直接取就行了，就像建立累加和数组一样，可以快速得到任意子数组的数字之和。

这里使用一个二维数组 pd，其中 pd[i][j] 表示范围为 [i, j] 的子串变为回文串需要改变的字母的个数，计算方法也比较简单，将其放到一个子函数 getChanges 中来处理，用两个指针 start 和 end 来指向子串的首尾位置，然后比较对应位置的字母是否相等，不相等的话结果 res 自增1即可。更新完了 pd 数组之后，就可以将子串s分割成任意的k个子串了，这里使用一个 dp 数组，其中 dp[i][j] 表示范围是 [0, j] 的子串分割为i个回文串所需的最小的字母改变个数。现在来看状态转移方程怎么写，首先分割为1个回文串的情况就是字符串s本身，只要知道其需要改变多少个字母变为回文串即可，这个可以在 pd 数组直接查到，所以 dp[1][j] 可以用 pd[0][j] 来初始化更新。然后就是更新分割数为2到k的情况，既然要更新分割为i个的 dp 值，那么至少要包括两个数字，所以 end 的范围是 [i-1, n-1]，然后就要尝试替换最后一个分割出的回文串的各种情况，起始位置 start 的范围是 [i-2, end-1]，则 dp[i][end] 可以用 dp[i-1][start] + pd[start+1][end] 来更新，因为范围 [0, start] 里分割了 i-1 个回文串，剩下的 [start+1, end] 范围内是另一个回文串。最终的结果就保存到了 dp[k][n-1] 中了，参见代码如下：

class Solution {
public:
    int palindromePartition(string s, int k) {
        int n = s.size();
        vector<vector<int>> pd(n, vector<int>(n)), dp(k + 1, vector<int>(n));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                pd[i][j] = getChanges(s, i, j);
            }
        }
        for (int i = 0; i < n; ++i) {
            dp[1][i] = pd[0][i];
        }
        for (int i = 2; i <= k; ++i) {
            for (int end = i - 1; end < n; ++end) {
                dp[i][end] = n;
                for (int start = end - 1; start >= i - 2; --start) {
                    dp[i][end] = min(dp[i][end], dp[i - 1][start] + pd[start + 1][end]);
                }
            }
        }
        return dp[k][n - 1];
    }
    int getChanges(string s, int start, int end) {
        int res = 0;
        while (start < end) {
            if (s[start++] != s[end--]) ++res;
        }
        return res;
    }
};

Github 同步地址:

#1278

类似题目：

Palindrome Partitioning IV

Palindrome Partitioning II

Palindrome Partitioning

参考资料：

https://leetcode.com/problems/palindrome-partitioning-iii/

https://leetcode.com/problems/palindrome-partitioning-iii/discuss/498677/Step-by-Step-solution-DP-(Java)

https://leetcode.com/problems/palindrome-partitioning-iii/discuss/442083/Simple-C%2B%2B-Dp-O(N2K)-Beats-100-with-Explanation

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）