分割回文串 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.

代码结果

运行时间: 48 ms, 内存: 16.1 MB

/*
 * 思路：
 * 1. 计算每个子串变成回文所需的最少修改次数。
 * 2. 使用动态规划来计算将字符串分割成k个子串的最少修改次数。
 * 3. 使用Java Stream简化部分代码。
 */

import java.util.stream.IntStream;

public class Solution {
    public int palindromePartition(String s, int k) {
        int n = s.length();
        int[][] cost = new int[n][n];

        // 计算每个子串变成回文的最少修改次数
        IntStream.range(2, n + 1).forEach(len -> {
            IntStream.range(0, n - len + 1).forEach(i -> {
                int j = i + len - 1;
                cost[i][j] = (s.charAt(i) == s.charAt(j)) ? cost[i + 1][j - 1] : cost[i + 1][j - 1] + 1;
            });
        });

        // 动态规划数组，dp[i][k] 表示前 i 个字符分割成 k 个子串的最小修改次数
        int[][] dp = new int[n + 1][k + 1];
        IntStream.range(0, n + 1).forEach(i -> Arrays.fill(dp[i], Integer.MAX_VALUE));
        dp[0][0] = 0;

        // 动态规划求解
        IntStream.range(1, n + 1).forEach(i -> {
            IntStream.range(1, k + 1).forEach(j -> {
                IntStream.range(0, i).forEach(m -> {
                    dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + cost[m][i - 1]);
                });
            });
        });

        return dp[n][k];
    }
}

解释

方法:

该题解采用动态规划的方法来解决问题。首先预处理出任意区间[i, j]转变成回文串所需的最小修改次数，存储在二维数组ss中。接着定义状态f[i][j]表示将字符串的前j个字符分割成i个回文子串所需的最小修改次数。状态转移方程是通过枚举上一个回文子串的结尾位置l来更新，即f[i][j] = min(f[i-1][l] + ss[l][j-1])，其中l从i-1到j-1遍历。最终答案为f[k][n]，即整个字符串分割成k个回文子串的最小修改次数。

时间复杂度:

O(n^3 + k*n^2)

空间复杂度:

O(n^2 + k*n)

代码细节讲解

🦆

题解中提到的二维数组ss的确切作用是什么？它如何帮助动态规划解决此问题？

▷

二维数组ss是用来存储任意子串[i, j]转变成回文串所需的最小修改次数。这个预处理步骤是为了支持动态规划中的状态转移。在动态规划过程中，每次计算分割出新的回文子串的代价时，可以直接使用ss数组得到任意子串成为回文串的修改次数，而不需要重新计算。这样大大减少了问题解决的时间复杂性，因为直接查表比重新计算每个子串是否为回文串要快得多。

🦆

在状态转移方程中，为什么选择遍历上一个回文子串的结尾位置l从i-1到j-1？

▷

在动态规划中，状态f[i][j]表示将字符串的前j个字符分割成i个回文子串的最小修改次数。遍历上一个回文子串的结尾位置l从i-1到j-1是因为，至少需要前i-1个字符来构成前i-1个回文子串。因此，l的最小值是i-1，确保每一个子串都至少有一个字符。l的最大值是j-1，意味着当前正在考虑的子串至少包含一个字符。这样的遍历范围确保了所有可能的子串划分都被考虑到，从而可以找到真正的最小修改次数来满足题目要求。

🦆

在动态规划数组f的初始化中，为什么f[0][0]初始化为0，而其他f[i][0]的值是什么？

▷

在动态规划数组f中，f[0][0]初始化为0是因为将长度为0的字符串分割成0个回文子串的修改次数自然是0（没有字符，也不需要分割）。对于其他的f[i][0]，这些表示试图将长度为0的字符串分割成多于0个回文子串，这在逻辑上是不可能的，因此应该初始化为无穷大（float('inf')），表示这种情况不可能发生。这样的初始化确保了动态规划在进行状态转移时，不会错误地考虑这些不合逻辑的情况。

分割回文串 III

题目描述

代码结果

解释

代码细节讲解

相关问题