目录

1278:分割回文串 III(1979 分)

力扣第 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 <= 100
  • s 中只含有小写英文字母。

相似问题:

分析

#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