1278：分割回文串 III（1979 分）

Ian

2019-12-01 约 628 字预计阅读 2 分钟次阅读

力扣第 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

按最后一个子串的长度，即可递推
子串变回文的修改次数可以预处理，节省时间
还可以用滚动数组优化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        w = [[0]*n for _ in range(n)]
        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                w[i][j] = w[i+1][j-1]+(s[i]!=s[j])
        f = [0]+[inf]*n
        for a in range(1,k+1):
            g = [inf]*(n+1)
            for i in range(a,n+1):
                g[i] = min(f[j]+w[j][i-1] for j in range(i))
            f = g
        return f[-1]

59 ms

#2

还可以在 f 上倒序递推，省去 g 数组
注意 a 对应的 f 值，只需要计算 f[a:]，节省时间

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        n = len(s)
        w = [[0]*n for _ in range(n)]
        for i in range(n-2,-1,-1):
            for j in range(i+1,n):
                w[i][j] = w[i+1][j-1]+(s[i]!=s[j])
        f = [0]+[inf]*n
        for a in range(1,k+1):
            for i in range(n,a-1,-1):
                f[i] = min(f[j]+w[j][i-1] for j in range(a-1,i))
        return f[-1]

31 ms

目录

1278：分割回文串 III（1979 分）

题目

分析

#1

#2

解答