Q131 分割回文串(palindrome partitioning)

解析思路

leetcode 中等难度,题目描述点击这里

本题对于从没接触过回溯题目的人来说可以说是非常困难了,并不容易。

首先题意是要求返回所有的分割组合,使分割后数组中的数都为回文数。

判断回文数的方法很简单,两个指针从两端往中间遍历即可,或者先用 dp 计算得到所有的回文数组合(本解答采用 dp),本题字符串最长为 16,暴力判断和 dp 区别不大。

关键是如何穷举出所有分割可能,简单的 for 循环显然是做不到的.需要用到回溯思想,具体分割方法可以先看下图:

字符串分割

字符串切分

将字符串切分结果展开成一棵树以后,可以发现结果集就是对这棵树进行深度优先搜索的遍历结果,理解清楚分割原理以后用代码实现就比较简单了:

dfs 分割字符串代码如下:

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
/**
* 分割字符串
*
* @param s 字符串
* @param index 子串的起始位置
* @param temp 临时存储已经分割后的字符串
* @param res 存储最终分割结果
*
* @author fanxb
* date 2022/3/9 16:39
*/
private void dfs(String s, int index, Stack<String> temp, List<List<String>> res ) {
if (index == s.length()) {
//当字符串起始位置超过字符串长度时说明本条链已经搜索完了
res.add(new ArrayList<>(temp));
return;
}
for (int i = index; i < s.length(); i++) {
String tempS = s.substring(index, i + 1);
temp.push(tempS);
dfs(s, i + 1, temp, res, dp);
//这里pop因为此路径已经处理完毕了,pop出去后,进行下一条路径处理
temp.pop();
}
}

dp 得到回文数分布情况

判断回文的递推关系比较容易写.定义 dp[i][j]表示从下标 i 到 j 的字符串是否回文,递推关系如下:

  1. dp[i][j]=true,i==j
  2. dp[i][j]=s[i]==s[j],i=j-1
  3. dp[i][j]=dp[i+1][j-1] && s[i]==s[j],其他情况

代码

经过上一节,现在我们已经能够穷举字符串所有的分割组合了,结合题意需要留下回文数组合,那么只需要进行剪枝操作即可(判断当前字符串片段是否回文,不回文就没必要继续当前路径)

完整代码如下:

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
public class Q131 {

public List<List<String>> partition(String s) {
//先用dp找到所有符合条件的回文
boolean[][] dp = new boolean[s.length()][s.length()];
for (int j = 0; j < dp.length; j++) {
for (int i = 0; i <= j; i++) {
if (i == j) {
dp[i][j] = true;
} else {
boolean b = s.charAt(i) == s.charAt(j);
if (i + 1 == j) {
dp[i][j] = b;
} else {
dp[i][j] = dp[i + 1][j - 1] && b;
}
}
}
}
List<List<String>> res = new ArrayList<>();
dfs(s, 0, new Stack<>(), res, dp);
return res;

}

/**
* 分割字符串
*
* @param s 字符串
* @param index 子串的起始位置
* @param temp 临时存储已经分割后的字符串
* @param res 存储最终分割结果
* @param dp dp结果
* @author fanxb
* date 2022/3/9 16:39
*/
private void dfs(String s, int index, Stack<String> temp, List<List<String>> res, boolean[][] dp) {
if (index == s.length()) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = index; i < s.length(); i++) {
if (dp[index][i + 1]) {
String tempS = s.substring(index, i + 1);
temp.push(tempS);
dfs(s, i + 1, temp, res, dp);
temp.pop();
}

}
}
}
本文原创发布于:https://blog.fleyx.com,转载请注明出处

如果本篇文章对您有帮助欢迎打赏哦!
微信打赏 支付宝打赏
关注公众号(烦嚣的人)
微信公众号