力扣第 165 场周赛第 4 题
题目
给你一个由小写字母组成的字符串 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 中只含有小写英文字母。
分析
#1
和系列的前两题相比，不能遍历前缀回文子串了，只能遍历每一个位置，但还是能用递归。
对每个位置 i ，分别计算 s[:i] 变成回文的最少修改数、s[i:] 分割 k-1 个回文子串的最少修改数，取和的最小值即可。
1
2
3
4
5
6
|
@lru_cache(None)
def palindromePartition(self, s: str, k: int) -> int:
cost = lambda s: sum(s[i] != s[-1-i] for i in range(len(s)//2))
if k == 1 or len(s) == 1:
return cost(s)
return min(cost(s[:i+1]) + self.palindromePartition(s[i+1:], k-1) for i in range(len(s)-1))
|
956 ms，空间占得较多
#2
可以改写成动态规划了。用 dp[i][k] 表示 s 的后缀子串 s[i:] 分成 k 个回文子串的最少分割数，状态转移方程为：
if k==1: dp[i][k] = cost(s[i:])
elif n-i<k: dp[i][k] = float('inf')
else: dp[i][k] = min(cost(s[i:j+1])+dp[j+1][k-1] for j in range(i, n-k+1))
1
2
3
4
5
6
7
8
9
10
|
def palindromePartition(self, s: str, k: int) -> int:
cost = lambda s: sum(s[i] != s[-1-i] for i in range(len(s)//2))
n = len(s)
dp = [[float('inf')]*(k+1) for _ in range(n)]
for i in range(n-1, -1, -1):
dp[i][1] = cost(s[i:])
for K in range(2, k+1):
for j in range(i, n-K+1):
dp[i][K] = min(dp[i][K], cost(s[i:j+1])+dp[j+1][K-1])
return dp[0][k]
|
时间复杂度 O(N^3*k)，980 ms
#3
可以预先保存 s 所有子串的 cost 值，节省时间。
1
2
3
4
5
6
7
8
9
10
11
|
def palindromePartition(self, s: str, k: int) -> int:
cost = lambda s: sum(s[i] != s[-1-i] for i in range(len(s)//2))
n = len(s)
costs = [[cost(s[l:r+1]) for r in range(n)] for l in range(n)]
dp = [[float('inf')]*(k+1) for _ in range(n)]
for i in range(n-1, -1, -1):
dp[i][1] = costs[i][n-1]
for K in range(2, k+1):
for j in range(i, n-K+1):
dp[i][K] = min(dp[i][K], costs[i][j]+dp[j+1][K-1])
return dp[0][k]
|
时间复杂度 O(N^3)，196 ms
#4
cost 的计算也可以用动态规划，状态转移方程为：
if l>=r: costs[l][r] = 0
elif s[l]==s[r]: costs[l][r] = costs[l+1][r-1]
else: osts[l][r] = costs[l+1][r-1] + 1
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def palindromePartition(self, s: str, k: int) -> int:
n = len(s)
costs = [[0]*n for _ in range(n)]
for span in range(1, n):
for l in range(n-span):
r = l+span
costs[l][r] = costs[l+1][r-1]+(0 if s[l]==s[r] else 1)
dp = [[float('inf')]*(k+1) for _ in range(n)]
for i in range(n-1, -1, -1):
dp[i][1] = costs[i][n-1]
for K in range(2, k+1):
for j in range(i, n-K+1):
dp[i][K] = min(dp[i][K], costs[i][j]+dp[j+1][K-1])
return dp[0][k]
|
时间复杂度 O(N^2*k)，152 ms