解析思路
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
|
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);
temp.pop();
}
}
|
dp 得到回文数分布情况
判断回文的递推关系比较容易写.定义 dp[i][j]表示从下标 i 到 j 的字符串是否回文，递推关系如下:
- dp[i][j]=true,i==j
- dp[i][j]=s[i]==s[j],i=j-1
- 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) {
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;
}
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();
}
}
}
}
|
如果本篇文章对您有帮助欢迎打赏哦！
关注公众号(烦嚣的人)
关注公众号(烦嚣的人) 