You are given a string s containing lowercase letters and an integer k. You need to :
- First, change some characters of
sto other lowercase English letters. - Then divide
sintoknon-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.sonly contains lowercase English letters.
Solution: DP
dp[i][k] := min changes to make s[0~i] into k palindromes
dp[i][k] = min(dp[j][k – 1] + cost(j + 1, i)) 0 <= j < i
ans = dp[n-1][K]
Time complexity: O(n^2 * K) = O(n^3)
Space complexity: O(n*n + n*K) = O(n^2)
C++
|
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 |
// Author: Huahua, 8 ms, 9.1 MB class Solution { public: int palindromePartition(string s, int K) { const int n = s.length(); auto minChange = [&](int i, int j) { int c = 0; while (i < j) if (s[i++] != s[j--]) ++c; return c; }; vector<vector<int>> cost(n, vector<int>(n)); for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) cost[i][j] = minChange(i, j); // dp[i][j] := min changes to make s[0~i] into k palindromes vector<vector<int>> dp(n, vector<int>(K + 1, INT_MAX / 2)); for (int i = 0; i < n; ++i) { dp[i][1] = cost[0][i]; for (int k = 1; k <= K; ++k) for (int j = 0; j < i; ++j) dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost[j + 1][i]); } return dp[n - 1][K]; } }; |
C++/DP+DP
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua, 4 ms, 9.1MB class Solution { public: int palindromePartition(string s, int K) { const int n = s.length(); vector<vector<int>> cost(n, vector<int>(n)); for (int l = 2; l <= n; ++l) for (int i = 0, j = l - 1; j < n; ++i, ++j) cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1]; vector<vector<int>> dp(n, vector<int>(K + 1, INT_MAX / 2)); for (int i = 0; i < n; ++i) { dp[i][1] = cost[0][i]; for (int k = 2; k <= K; ++k) for (int j = 0; j < i; ++j) dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost[j + 1][i]); } return dp[n - 1][K]; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua import functools class Solution: def palindromePartition(self, s: str, K: int) -> int: @functools.lru_cache(None) def cost(i: int, j: int) -> int: if i >= j: return 0 return cost(i + 1, j - 1) + (1 if s[i] != s[j] else 0) @functools.lru_cache(None) def dp(i: int, k: int) -> int: if k == 1: return cost(0, i) if k == i + 1: return 0 if k > i + 1: return 1**9 return min([dp(j, k - 1) + cost(j + 1, i) for j in range(i)]) return dp(len(s) - 1, K) |