Leetcode-1278.Palindrome Partitioning III [C++][Java]

发布于:2025-03-17 ⋅ 阅读:(26) ⋅ 点赞:(0)

目录

一、题目描述

二、解题思路

【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];
    }
}


网站公告

今日签到

点亮在社区的每一天
去签到