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 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.

二、解题思路

• 时间复杂度：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];
    }
}