leetcode 1278

问题

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:

1
2
3
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:

1
2
3
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:

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

Constraints:

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

分析

cost[i][j] 表示字符串 s[i...j] 转化成回文需要替换的字符。dp[i][j] 表示字符串 s[i:] 切分成 j 块的子问题的答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int palindromePartition(string s, int k) {
        int n = s.size();
        vector<vector<int>> cost(n, vector<int>(n, 0));
        for (int i = n-1; i >= 0; --i) {
            cost[i][i] = 0;
            for (int j = i+1; j < n; ++j) {
                if (j == i+1)
                    cost[i][j] = s[i]==s[j]? 0: 1;
                else
                    cost[i][j] = cost[i+1][j-1] + (s[i]==s[j]? 0: 1);
            }
        }
        vector<vector<int>> dp(n+1, vector<int>(k+1, -1));
        return dfs(cost, dp, s, 0, k);
    }

    int dfs(vector<vector<int>> &cost, vector<vector<int>> &dp,
            const string &s, int i, int k) {
            if (dp[i][k] >= 0) return dp[i][k];
            if (i >= s.size()) return 0;
            if (k == 1) return cost[i][s.size()-1];
            int ret = INT_MAX;
            for (int j = i; s.size()-j >= k; ++j) {
                ret = min(ret, cost[i][j] + dfs(cost, dp, s, j+1, k-1));
            }
            return dp[i][k] = ret;
        }
    
};