LeetCode 题解工作台
分割回文串 III
给你一个由小写字母组成的字符串 s ，和一个整数 k 。 请你按下面的要求分割字符串： 首先，你可以将 s 中的部分字符修改为其他的小写英文字母。 接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。 请返回以这种方式分割字符串所需修改的最少字符数。 示例 1： 输入： s…
2
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们定义 表示将字符串 的前 个字符分割成 个回文串所需要的最少修改次数，我们假定 下标从 开始，答案为 。 对于 ，我们可以枚举第 个回文串的最后一个字符的位置 ，那么 就等于 $f[h][j-1] + g[h][i-1]$ 的较小值，其中 表示将字符串 变成回文串所需要的最少修改次数（这一部分我们可以通过预处理得到，时间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个由小写字母组成的字符串 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 <= 100s中只含有小写英文字母。
解题思路
方法一：动态规划
我们定义 表示将字符串 的前 个字符分割成 个回文串所需要的最少修改次数，我们假定 下标从 开始，答案为 。
对于 ，我们可以枚举第 个回文串的最后一个字符的位置 ，那么 就等于 的较小值，其中 表示将字符串 变成回文串所需要的最少修改次数（这一部分我们可以通过预处理得到，时间复杂度 。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
class Solution:
def palindromePartition(self, s: str, k: int) -> int:
n = len(s)
g = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
g[i][j] = int(s[i] != s[j])
if i + 1 < j:
g[i][j] += g[i + 1][j - 1]
f = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, min(i, k) + 1):
if j == 1:
f[i][j] = g[0][i - 1]
else:
f[i][j] = inf
for h in range(j - 1, i):
f[i][j] = min(f[i][j], f[h][j - 1] + g[h][i - 1])
return f[n][k]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2 * k) due to iterating over all substrings for each partition count, and space complexity is O(n^2 + n*k) for storing palindrome costs and DP states. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidate precomputes substring palindrome costs efficiently.
- question_mark
Look for correct DP state definition and transition logic.
- question_mark
Verify handling of edge cases where k equals string length or 1.
常见陷阱
外企场景- error
Forgetting to precompute palindrome costs leading to TLE.
- error
Incorrect DP initialization causing invalid minimal values.
- error
Overlooking edge cases such as single-character substrings or k equal to string length.
进阶变体
外企场景- arrow_right_alt
Minimizing changes to form exactly k palindromic substrings with additional character constraints.
- arrow_right_alt
Allowing deletions instead of changes to form k palindromes.
- arrow_right_alt
Extending the problem to partition into palindromes with maximum length constraints.