解析思路
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(); }
} } }
|
如果本篇文章对您有帮助欢迎打赏哦!
关注公众号(烦嚣的人)