题目描述
给你一个字符串 s 和一个整数 k，请将 s 划分为 k 个 非空子串 ，使得将每个子串变为 半回文串 所需的字符修改次数之和最小。
返回所需的 最少 字符修改次数。
半回文串 是一类特殊的字符串：它可以按照某种重复模式拆分后，使每一组都成为 回文串 。判断一个字符串是否为半回文串的方法如下：
- 选择该字符串长度的一个正因数
d。其中，d 的取值范围是从 1 到严格小于字符串长度的所有正因数。对于长度为 1 的字符串，根据这一定义，它不存在合法的因数，因为唯一的因数就是其长度本身，而这是不允许的。 - 对于给定的因数
d，将字符串按长度为 d 的重复模式分组。具体来说，第 1 组由位置 1、1 + d、1 + 2d、…… 上的字符组成；第 2 组由位置 2、2 + d、2 + 2d、…… 上的字符组成；以此类推。 - 如果这些分组中的每一组都是回文串，则该字符串被视为半回文串。
以字符串 "abcabc" 为例：
"abcabc" 的长度为 6。合法的因数有 1、2 和 3。- 当
d = 1 时：整个字符串 "abcabc" 构成一组。它不是回文串。 - 当
d = 2 时： - 第 1 组（位置
1, 3, 5）："acb" - 第 2 组（位置
2, 4, 6）："bac" - 这两组都不是回文串。
- 当
d = 3 时： - 第 1 组（位置
1, 4）："aa" - 第 2 组（位置
2, 5）："bb" - 第 3 组（位置
3, 6）："cc" - 所有分组都是回文串。因此，
"abcabc" 是一个半回文串。
示例 1：
输入： s = "abcac", k = 2
输出： 1
解释： 将 s 划分为 "ab" 和 "cac"。"cac" 本身已经是半回文串。将 "ab" 改为 "aa" 后，它在 d = 1 时成为半回文串。
示例 2：
输入： s = "abcdef", k = 2
输出： 2
解释： 将其划分为子串 "abc" 和 "def"。这两个子串各自都需要修改 1 个字符才能变成半回文串。
示例 3：
输入： s = "aabbaa", k = 3
输出： 0
解释： 将其划分为子串 "aa"、"bb" 和 "aa"。它们都已经是半回文串。
提示：
2 <= s.length <= 2001 <= k <= s.length / 2s 仅由小写英文字母组成。
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | class Solution:
def minimumChanges(self, s: str, k: int) -> int:
n = len(s)
g = [[inf] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(i, n + 1):
m = j - i + 1
for d in range(1, m):
if m % d == 0:
cnt = 0
for l in range(m):
r = (m // d - 1 - l // d) * d + l % d
if l >= r:
break
if s[i - 1 + l] != s[i - 1 + r]:
cnt += 1
g[i][j] = min(g[i][j], cnt)
f = [[inf] * (k + 1) for _ in range(n + 1)]
f[0][0] = 0
for i in range(1, n + 1):
for j in range(1, k + 1):
for h in range(i - 1):
f[i][j] = min(f[i][j], f[h][j - 1] + g[h + 1][i])
return f[n][k]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 | class Solution {
public int minimumChanges(String s, int k) {
int n = s.length();
int[][] g = new int[n + 1][n + 1];
int[][] f = new int[n + 1][k + 1];
final int inf = 1 << 30;
for (int i = 0; i <= n; ++i) {
Arrays.fill(g[i], inf);
Arrays.fill(f[i], inf);
}
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
int m = j - i + 1;
for (int d = 1; d < m; ++d) {
if (m % d == 0) {
int cnt = 0;
for (int l = 0; l < m; ++l) {
int r = (m / d - 1 - l / d) * d + l % d;
if (l >= r) {
break;
}
if (s.charAt(i - 1 + l) != s.charAt(i - 1 + r)) {
++cnt;
}
}
g[i][j] = Math.min(g[i][j], cnt);
}
}
}
}
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
for (int h = 0; h < i - 1; ++h) {
f[i][j] = Math.min(f[i][j], f[h][j - 1] + g[h + 1][i]);
}
}
}
return f[n][k];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 | class Solution {
public:
int minimumChanges(string s, int k) {
int n = s.size();
int g[n + 1][n + 1];
int f[n + 1][k + 1];
memset(g, 0x3f, sizeof(g));
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
int m = j - i + 1;
for (int d = 1; d < m; ++d) {
if (m % d == 0) {
int cnt = 0;
for (int l = 0; l < m; ++l) {
int r = (m / d - 1 - l / d) * d + l % d;
if (l >= r) {
break;
}
if (s[i - 1 + l] != s[i - 1 + r]) {
++cnt;
}
}
g[i][j] = min(g[i][j], cnt);
}
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
for (int h = 0; h < i - 1; ++h) {
f[i][j] = min(f[i][j], f[h][j - 1] + g[h + 1][i]);
}
}
}
return f[n][k];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 | func minimumChanges(s string, k int) int {
n := len(s)
g := make([][]int, n+1)
f := make([][]int, n+1)
const inf int = 1 << 30
for i := range g {
g[i] = make([]int, n+1)
f[i] = make([]int, k+1)
for j := range g[i] {
g[i][j] = inf
}
for j := range f[i] {
f[i][j] = inf
}
}
f[0][0] = 0
for i := 1; i <= n; i++ {
for j := i; j <= n; j++ {
m := j - i + 1
for d := 1; d < m; d++ {
if m%d == 0 {
cnt := 0
for l := 0; l < m; l++ {
r := (m/d-1-l/d)*d + l%d
if l >= r {
break
}
if s[i-1+l] != s[i-1+r] {
cnt++
}
}
g[i][j] = min(g[i][j], cnt)
}
}
}
}
for i := 1; i <= n; i++ {
for j := 1; j <= k; j++ {
for h := 0; h < i-1; h++ {
f[i][j] = min(f[i][j], f[h][j-1]+g[h+1][i])
}
}
}
return f[n][k]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 | function minimumChanges(s: string, k: number): number {
const n = s.length;
const g = Array.from({ length: n + 1 }, () => Array.from({ length: n + 1 }, () => Infinity));
const f = Array.from({ length: n + 1 }, () => Array.from({ length: k + 1 }, () => Infinity));
f[0][0] = 0;
for (let i = 1; i <= n; ++i) {
for (let j = 1; j <= n; ++j) {
const m = j - i + 1;
for (let d = 1; d < m; ++d) {
if (m % d === 0) {
let cnt = 0;
for (let l = 0; l < m; ++l) {
const r = (((m / d) | 0) - 1 - ((l / d) | 0)) * d + (l % d);
if (l >= r) {
break;
}
if (s[i - 1 + l] !== s[i - 1 + r]) {
++cnt;
}
}
g[i][j] = Math.min(g[i][j], cnt);
}
}
}
}
for (let i = 1; i <= n; ++i) {
for (let j = 1; j <= k; ++j) {
for (let h = 0; h < i - 1; ++h) {
f[i][j] = Math.min(f[i][j], f[h][j - 1] + g[h + 1][i]);
}
}
}
return f[n][k];
}
|
方法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80 | class Solution {
static int inf = 200;
List<Integer>[] factorLists;
int n;
int k;
char[] ch;
Integer[][] cost;
public int minimumChanges(String s, int k) {
this.k = k;
n = s.length();
ch = s.toCharArray();
factorLists = getFactorLists(n);
cost = new Integer[n + 1][n + 1];
return calcDP();
}
static List<Integer>[] getFactorLists(int n) {
List<Integer>[] l = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
l[i] = new ArrayList<>();
l[i].add(1);
}
for (int factor = 2; factor < n; factor++) {
for (int num = factor + factor; num <= n; num += factor) {
l[num].add(factor);
}
}
return l;
}
int calcDP() {
int[] dp = new int[n];
for (int i = n - k * 2 + 1; i >= 1; i--) {
dp[i] = getCost(0, i);
}
int bound = 0;
for (int subs = 2; subs <= k; subs++) {
bound = subs * 2;
for (int i = n - 1 - k * 2 + subs * 2; i >= bound - 1; i--) {
dp[i] = inf;
for (int prev = bound - 3; prev < i - 1; prev++) {
dp[i] = Math.min(dp[i], dp[prev] + getCost(prev + 1, i));
}
}
}
return dp[n - 1];
}
int getCost(int l, int r) {
if (l >= r) {
return inf;
}
if (cost[l][r] != null) {
return cost[l][r];
}
cost[l][r] = inf;
for (int factor : factorLists[r - l + 1]) {
cost[l][r] = Math.min(cost[l][r], getStepwiseCost(l, r, factor));
}
return cost[l][r];
}
int getStepwiseCost(int l, int r, int stepsize) {
if (l >= r) {
return 0;
}
int left = 0;
int right = 0;
int count = 0;
for (int i = 0; i < stepsize; i++) {
left = l + i;
right = r - stepsize + 1 + i;
while (left + stepsize <= right) {
if (ch[left] != ch[right]) {
count++;
}
left += stepsize;
right -= stepsize;
}
}
return count;
}
}
|