Palindrome Paritioning III

题目

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 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个非空回文子串
• 求最小的更改字符的次数
• 强烈提示：字符串长度最长100 –> 时间复杂度最多10^6 （也就是n^3）

理解例子

例子 1

• S：abc
• K：2
• 结果：1
• 将S划分为两个部分：ab、c，修改ab中的一个字符即可变成回文

例子 2

• S：aabbc
• K：3
• 结果：0
• 将S划分为：aa、bb、c，所有的都是回文，不需要更改。

思路

• 强烈提示：数据规模 – 10^2，也就是说期望的时间复杂度为 n^3 or n^2 * k
• 计数问题，一般可以用动态规划解决。
• 题目要求k次划分，如何划分需要解决，使用动态规划一般和 k-1 有关系。
• 划分后，针对子串如何更换，也需要解决，并且求最小值。
• 所以就两个子问题：1. 如何划分。2.如何更换。
• dp_[i][k],表示0…i的字符，进行k次划分的最小交换次数

划分

• 可以把划分想象成两个部分，左边和右边。
• 左边：是从 0…j 进行 k-1 次的划分。右边： 一次划分（）。
• dp_[i][k] = min{dp_[i][k], dp_[j][k-1] + dp_change[j][i]}
• dp_change[j][i] 表示从j到i 的最小更换次数。

更改字符

• 如果划分确定后，如何更改字符就比较好确定了
• 回文字符串应该从中间开始构建，并且向两边拓展
• 如果前后两个字符相等(str[i] == str[j]): dp_change[i][j] = dp_change[i+1][j-1]
• 如果前后两个字符不等(str[i] != str[j]): dp_change[i][j] = 1 + dp_change[i+1][j-1]
• dp_change[i][j] = (str[i] != str[j]) + dp_change[i+1][j-1]

解决了以上两个问题，那完整的问题，就解决了

流程

• 异常判断
• 针对所有的位置，尝试所有的分割，

伪代码

int palindromePartition(string &str, int k){

}

代码

class Solution {
public:
    int findMediaSortedArrays(vector<int> &nums1, vector<int> &nums2) {
        const int m = nums1.size();
        const int n = nums2.size();
        if (m > n) return findMediaSortedArrays(nums2, nums1);

    }
};

时间复杂度

如一开始分析：时间复杂度：线性时间 \(\mathcal{O(n)}\)

空间复杂度

额外申请了和一个链表，因此空间复杂度也为 \(\mathcal{O(max(len(l1), len(l2)))}\)