Leetcode-1278.Palindrome Partitioning III [C++][Java]
目录
一、题目描述
二、解题思路
【C++】
【Java】
Leetcode-1278.Palindrome Partitioning IIIhttps://leetcode.com/problems/palindrome-partitioning-iii/description/1278. 分割回文串 III - 力扣(LeetCode)1278. 分割回文串 III - 给你一个由小写字母组成的字符串 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 中只含有小写英文字母。
https://leetcode.cn/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
intok
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.
二、解题思路
-
时间复杂度:O(n^2*k)
-
空间复杂度:O(n^2+n*k)
【C++】
class Solution {
public:
int palindromePartition(string s, int k) {
vector<vector<int>> change(s.size(), vector<int>(s.size(), 0));
for (int l = s.size() - 2; l >= 0; --l) {
for (int r = l + 1; r < s.size(); ++r) {
change[l][r] = change[l + 1][r - 1] + (s[l] == s[r] ? 0 : 1);
}
}
vector<vector<int>> dp(k, vector<int>(s.size(), INT_MAX));
dp[0] = move(change[0]);
for (int i = 1; i < k; ++i) {
for (int r = i; r <= s.size() - k + i; ++r) {
for (int l = i; l <= r; ++l) {
dp[i][r] = min(dp[i][r], dp[i - 1][l - 1] + change[l][r]);
}
}
}
return dp[k - 1][s.size() - 1];
}
};
【Java】
class Solution {
public int palindromePartition(String s, int k) {
int[][] change = new int[s.length()][s.length()];
for (int l = s.length() - 2; l >= 0; --l) {
for (int r = l + 1; r < s.length(); ++r) {
change[l][r] = change[l + 1][r - 1] + (s.charAt(l) == s.charAt(r) ? 0 : 1);
}
}
int[][] dp = new int[k][s.length()];
for (int i = 0; i < k; ++i) Arrays.fill(dp[i], Integer.MAX_VALUE);
dp[0] = change[0];
for (int i = 1; i < k; ++i) {
for (int r = i; r <= s.length() - k + i; ++r) {
for (int l = i; l <= r; ++l) {
dp[i][r] = Math.min(dp[i][r], dp[i - 1][l - 1] + change[l][r]);
}
}
}
return dp[k - 1][s.length() - 1];
}
}