class Solution {
public:
int palindromePartition(string s, int k) {
}
};
1278. 分割回文串 III
给你一个由小写字母组成的字符串 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 中只含有小写英文字母。原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2023-06-15 14:43:00
/*
check(l, r) 函数判断将s[l:r+1]变成回文串所需的操作数，memo记忆化
开dp并初始化 dp[i][j]表示将s 的前j个字符分割成i段回文串所需的最少操作数
状态转移方程为dp[i][j] = min(dp[i][j], check(k - 1, j - 1) + dp[i - 1][k - 1])
返回答案 dp[k][n]
*/
func palindromePartition(s string, k int) int {
n := len(s)
// check函数判断将s[l:r+1]变成回文串所需的操作数，memo记忆化
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, n)
for j := range memo[i] {
memo[i][j] = -1
}
}
check := func(l, r int) (ans int) {
if memo[l][r] != -1 {
return memo[l][r]
}
i, j := l, r
for i < j {
if s[i] != s[j] {
ans++
}
i, j = i + 1, j - 1
}
memo[l][r] = ans
return
}
// 开dp并初始化
dp := make([][]int, k + 1)
for i := range dp {
dp[i] = make([]int, n + 1)
for j := range dp[i] {
dp[i][j] = n
}
}
for i := 1; i <= n; i++ {
dp[1][i] = check(0, i - 1)
}
for i := 1; i <= k; i++ {
dp[i][i] = 0
}
// 状态转移求解
for i := 2; i <= k; i++ {
for j := i + 1; j <= n; j++ {
for k := i; k <= j; k++ {
dp[i][j] = min(dp[i][j], check(k - 1, j - 1) + dp[i - 1][k - 1])
}
}
}
// 返回答案
return dp[k][n]
}
func min(x, y int) int {if x < y {return x}; return y}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.2 MB, 提交时间: 2023-06-15 14:39:37
func palindromePartition(s string, k int) int {
//状态转移方程
//f[i][j] 前[0-i]字符，分割成j个回文字符串，有多少种分法
//f[i][j] = f[x0][j-1] + cost(s, x0, i-1)
f := make([][]int, len(s) + 1)
for i := 0; i < len(f); i++ {
f[i] = make([]int, len(s) +1)
for j := 0; j < len(f[i]); j++ {
f[i][j] = math.MaxInt32
}
}
f[0][0] = 0 //[0]字符分割0份，需要0次修改
f[1][1] = 0 //[0-1]字符分割1次， 需要0次修改
//[left,right]字符修改位回文需要多少次修改
cost := func(left int, right int) int {
ret := 0
for left < right {
if s[left] != s[right] {
ret++
}
left++
right--
}
return ret
}
//遍历s, 前[0-i]字符
for i := 0; i < len(s); i++ {
//遍历， 分割成j个字符串
for j := 1; j <= min(i+1, k); j++ {
//如果分割成1个字符串
//f[i][j] = f[i][1] : [0-i]字符分割成1个字符串需要多少次修改
//计算字符[0-i]需要多少次修改
if j == 1 {
f[i][j] = cost(0, i)
} else {
//如果分割成多个字符串
//第j个字符串从哪个字符开始遍历?
//第j个字符串前面有j-1个字符串，所以至少有j-1个字符
//j-1个字符：[0-j-2]
//m从j-2开始遍历，到i结束，且不包括i， 因为i是最后一个字符索引，必须在第j个字符串中
for m := j-2; m < i; m++ {
//f[i][j] = f[m][j-1] + cost(m+1,i)
//[0-i]字符分个成j子字符串需要修改多少次 =
//[0-m]字符分割成j-1个字符串需要修改次数 + [m+1,i]字符串需要修改次数
f[i][j] = min(f[i][j], f[m][j-1] + cost(m+1,i))
}
}
}
}
return f[len(s) - 1][k]
}
func min(a, b int) int { if a < b { return a }; return b }
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-06-15 14:38:36
var cache [][]int // cache记录 前i个字符组成的字符串 切割出j个 字符串所花费的最小代价
func palindromePartition(s string, k int) int {
lens := len(s)
if lens <= k {
return 0
}
cache = make([][]int, lens)
for i := 0; i < lens; i++ {
cache[i] = make([]int, k)
for j := 0; j < k; j++ {
cache[i][j] = math.MinInt32
}
}
cs := []byte(s)
return dfs(cs, 0, k-1)
}
func dfs(cs []byte, start int, k int) int {
// len - start代表当前要切割的字符串的长度
// 如果这个长度小于等于要切割的次数意味着没办法继续切割了
if len(cs)-start <= k {
return -1
}
if cache[start][k] != math.MinInt32 {
return cache[start][k]
}
// k <= 0 时 还有剩余的字符串 直接计算最小代价
if k <= 0 {
cache[start][k] = cost(cs, start, len(cs))
return cache[start][k]
}
minCost := math.MaxInt32
for i := 1; i <= len(cs); i++ {
// 计算 start 到 start + i 的最小代价
cost := cost(cs, start, start+i)
// 接着计算后面字符串的最小代价
sub := dfs(cs, start+i, k-1)
if sub == -1 {
break
}
minCost = min(minCost, cost+sub)
}
// 将最小代价记录下来
cache[start][k] = minCost
return cache[start][k]
}
func cost(cs []byte, start int, end int) int {
res := 0
left := start
right := end - 1
for left < right {
if cs[left] != cs[right] {
res++
}
left++
right--
}
return res
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
python3 解法, 执行用时: 88 ms, 内存消耗: 16.3 MB, 提交时间: 2023-06-15 14:37:50
class Solution:
def palindromePartition(self, s: str, k: int) -> int:
n = len(s)
# 计算所有的子串变为回文串需要多少操作次数
dp = [[0]*n for _ in range(n)]
for i in range(n-2, -1, -1):
dp[i][i+1] = int(s[i] != s[i+1])
for j in range(i+2, n):
dp[i][j] = dp[i+1][j-1]+int(s[i] != s[j])
# 计算将第i个字符分到第j个子字符串需要修改的个数
ans = [[0]*k for _ in range(n)]
for i in range(1, n):
ans[i][0] = dp[0][i]
for j in range(1, min(k, i+1)):
ans[i][j] = min([ans[p][j-1] + dp[p+1][i] for p in range(j-1, i)])
return ans[n-1][k-1]
cpp 解法, 执行用时: 8 ms, 内存消耗: 6.6 MB, 提交时间: 2023-06-15 14:37:17
class Solution {
public:
int palindromePartition(string& s, int k) {
int n = s.size();
vector<vector<int>> cost(n, vector<int>(n));
for (int span = 2; span <= n; ++span) {
for (int i = 0; i <= n - span; ++i) {
int j = i + span - 1;
cost[i][j] = cost[i + 1][j - 1] + (s[i] == s[j] ? 0 : 1);
}
}
vector<vector<int>> f(n + 1, vector<int>(k + 1, INT_MAX));
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= min(k, i); ++j) {
if (j == 1) {
f[i][j] = cost[0][i - 1];
}
else {
for (int i0 = j - 1; i0 < i; ++i0) {
f[i][j] = min(f[i][j], f[i0][j - 1] + cost[i0][i - 1]);
}
}
}
}
return f[n][k];
}
};
python3 解法, 执行用时: 128 ms, 内存消耗: 16.3 MB, 提交时间: 2023-06-15 14:37:00
class Solution:
def palindromePartition(self, s: str, k: int) -> int:
n = len(s)
cost = [[0] * n for _ in range(n)] # 优化cost(l, r)
for span in range(2, n + 1):
for i in range(n - span + 1):
j = i + span - 1
cost[i][j] = cost[i + 1][j - 1] + (0 if s[i] == s[j] else 1)
f = [[10**9] * (k + 1) for _ in range(n + 1)]
f[0][0] = 0
for i in range(1, n + 1):
for j in range(1, min(k, i) + 1):
if j == 1:
f[i][j] = cost[0][i - 1]
else:
for i0 in range(j - 1, i):
f[i][j] = min(f[i][j], f[i0][j - 1] + cost[i0][i - 1])
return f[n][k]
cpp 解法, 执行用时: 24 ms, 内存消耗: 6.3 MB, 提交时间: 2023-06-15 14:35:42
class Solution {
public:
int cost(string& s, int l, int r) {
int ret = 0;
for (int i = l, j = r; i < j; ++i, --j) {
if (s[i] != s[j]) {
++ret;
}
}
return ret;
}
int palindromePartition(string& s, int k) {
int n = s.size();
vector<vector<int>> f(n + 1, vector<int>(k + 1, INT_MAX));
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= min(k, i); ++j) {
if (j == 1) {
f[i][j] = cost(s, 0, i - 1);
}
else {
for (int i0 = j - 1; i0 < i; ++i0) {
f[i][j] = min(f[i][j], f[i0][j - 1] + cost(s, i0, i - 1));
}
}
}
}
return f[n][k];
}
};
python3 解法, 执行用时: 1328 ms, 内存消耗: 16.2 MB, 提交时间: 2023-06-15 14:35:27
'''
动态规划
f[i][j] 表示对于字符串 s 的前 i 个字符，将它分割成 j 个非空且不相交的回文串，最少需要修改的字符数。
在进行状态转移时，我们可以枚举第 j 个回文串的起始位置 i0，那么就有如下的状态转移方程：
f[i][j] = min(f[i0][j - 1] + cost(s, i0 + 1, i))
其中 cost(s, l, r) 表示将 s 的第 l 个到第 r 个字符组成的子串变成回文串，最少需要修改的字符数。
'''
class Solution:
def palindromePartition(self, s: str, k: int) -> int:
def cost(l, r):
ret, i, j = 0, l, r
while i < j:
ret += (0 if s[i] == s[j] else 1)
i += 1
j -= 1
return ret
n = len(s)
f = [[10**9] * (k + 1) for _ in range(n + 1)]
f[0][0] = 0
for i in range(1, n + 1):
for j in range(1, min(k, i) + 1):
if j == 1:
f[i][j] = cost(0, i - 1)
else:
for i0 in range(j - 1, i):
f[i][j] = min(f[i][j], f[i0][j - 1] + cost(i0, i - 1))
return f[n][k]