分割回文串II

LeetCode每日一题,132. Palindrome Partitioning II

先看题目描述

6QeyQO.png

大意就是给定一个字符串 s,让我们将 s 分割成多个回文子串,并返回最小的分割次数

算法和思路

动态规划

  • 状态方程定义:f[i] 表示将子串 s[0:i] 分割为多个回文子串的最小分割次数
  • 状态转移方程:若 s[0:i] 为回文串,则 f[i] = 0;否则 f[i] = min{f[j]} + 1,其中 0 <= j < i 且 s[j + 1:i] 为回文串
  • 最后返回 f[len - 1] 即可

即我们枚举最后一个回文串的起始位置 j + 1,保证 s[j + 1:i] 是一个回文串,那么 f[i] 就可以从 f[j] 转移而来,附加一次额外的分割次数。若 s[0:i] 本身就是回文串的话,则不用分割,其最小分割次数为 0

至于如何快速的判断 s[j + 1:i] 是否为回文串,我们可以使用动态规划进行预处理

  • 状态方程定义:布尔数组 dp[i][j] 表示子串 s[i:j] 是否为回文串
  • 状态转移方程:dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]

将 dp 数组预先构建好后便可在 O(1) 的时间内判断子串 s[j + 1:i] 是否为回文串

ps:感觉这题中动态数组 f 的状态转移方程有点类似 LIS问题(最长上升序列问题)的状态转移方程,其状态转移方程为 f[i] = max{f[j]} + 1,其中 0 <= j < i 且 nums[j] < nums[i]

算法源码

动态规划

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
import java.util.Arrays;

class Solution {
public int minCut(String s) {
int len = s.length();
int[] f = new int[len];
char[] cs = s.toCharArray();
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
for (int i = len - 2; i >= 0; i--) {
for (int j = i + 1; j < len; j++) {
if (j - i <= 2) {
dp[i][j] = cs[i] == cs[j];
} else {
dp[i][j] = dp[i + 1][j - 1] && cs[i] == cs[j];
}
}
}
Arrays.fill(f, Integer.MAX_VALUE);
for (int i = 0; i < len; i++) {
if (dp[0][i]) {
f[i] = 0;
} else {
for (int j = 0; j < i; j++) {
if (dp[j + 1][i]) {
f[i] = Math.min(f[i], f[j] + 1);
}
}
}
}
return f[len - 1];
}
}

下面是使用 回溯搜索 + 动态规划 实现的代码,基本上和昨天的题思路是一致的,结果跑超时了

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
class Solution {
private int len;
private int count = -1;
private int ans = Integer.MAX_VALUE;
private boolean[][] dp;

public int minCut(String s) {
len = s.length();
char[] cs = s.toCharArray();
dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
for (int i = len - 2; i >= 0; i--) {
for (int j = i + 1; j < len; j++) {
if (j - i <= 2) {
dp[i][j] = cs[i] == cs[j];
} else {
dp[i][j] = dp[i + 1][j - 1] && cs[i] == cs[j];
}
}
}
dfs(s, 0);
return ans;
}

private void dfs(String s, int index) {
if (index == len) {
ans = Math.min(ans, count);
return;
}
for (int i = len - 1; i >= index; i--) {
if (dp[index][i]) {
count++;
dfs(s, i + 1);
count--;
}
}
}
}