我是通过idea的leetcode插件获取题目做题的，所以题目描述基本都会有注释符号哈
这套题解题的时候参照LeetCode的其中一个方案，链接如下
1. 题目描述
* // [131] 分隔回文串
* // 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
* //
* // 返回 s 所有可能的分割方案。
* //
* // 示例:
* //
* // 输入: "aab"
* //输出:
* //[
* // ["aa","b"],
* // ["a","a","b"]
* //]
* // Related Topics 回溯算法
复制代码2. 思路分析
这道题的想要的是所有的方案，也就是说每一个方案，List 里面的值都是回文数。
我们根据第一个回文串的出现的位置，作为第一次的切分点，将左串以及右串分出来，左串加入分割方案的List中，然后在对右串进行判断，对第一个回文串出现的位置进行切割。
退出的条件为右串的长度为0，也就没法分割了，到这一步的时候，将 分割方案加入结果集中。
3. AC代码
public class No131 {
public static List<List<String>> partition(String s) {
// return method1(s);
return method2(s);
}
// ------ method1 start --------
/**
* 构造两个 List
* 接收结果 List<List<String>> 的 re
* 接收每一个分割方案 ArrayList<String> 的 temp
*
* 执行耗时:11 ms,击败了62.28% 的Java用户
* 内存消耗:51.3 MB,击败了87.81% 的Java用户
*
* @param s
* @return
*/
private static List<List<String>> method1(String s) {
List<List<String>> re = new ArrayList<List<String>>();
traceBack(re,s,new ArrayList<String>());
return re;
}
/**
* 对字符串进行遍历截取,分为左串和右串，如果是左串是回文串，加入数组 temp 中，对右串进行下一次的tracBack
*
* @param re
* @param s
* @param temp
*/
private static void traceBack(List<List<String>> re, String s, ArrayList<String> temp) {
if(s==null || s.length()==0) {
re.add(new ArrayList<String>(temp));
} else {
for (int i = 1; i <= s.length(); i++) {
// 之前用过的判断字符串
if(isPalidrome(s.substring(0,i))) {
// 满足就加入
temp.add(s.substring(0,i));
// System.out.println(s.substring(0,i))
// 注意此处传入的 字符串值为 s.substring(i)
// 已经将第一个字符串切出来加入 temp List 里面了
traceBack(re,s.substring(i),temp);
// 当前的 List 已经加入到了结果集中，一个个往回删除，进入 下一个循环的判断， 即 s.subString(0,i+1)
temp.remove(temp.size()-1);
}
}
}
}
/**
* 回文串判断
*
* @param s
* @return
*/
private static boolean isPalidrome(String s) {
int left = 0;
int right = s.length()-1;
while(left < right) {
if(s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
// ------ method1 end --------
// ------ method2 start --------
// 运行测试要通过，把res放在 method2中，然后在dfs方法加上 res这个参数
public static List<List<String>> res = new ArrayList<>();
/**
* 方法2，思路与方法1类似，比较不同在于一开始构造了一个回文数的表，方便验证是否是回文数
*
* 执行耗时:8 ms,击败了91.72% 的Java用户
* 内存消耗:52.4 MB,击败了47.78% 的Java用户
*/
public static List<List<String>> method2(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
// (j - i < 2 || dp[i + 1][j - 1]) 没有间隔或者 收缩前一位也是回文数，自上而下 ，这段细品一下
if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) dp[i][j] = true;
}
}
dfs(s, 0, n, new ArrayList<>(), dp);
return res;
}
private static void dfs(String s, int i, int n, List<String> sub, boolean[][] dp) {
if (i == n) {
res.add(new ArrayList<>(sub));
return;
}
for (int j = i; j < n; j++) {
if (dp[i][j]) {
sub.add(s.substring(i, j + 1));
dfs(s, j + 1, n, sub, dp);
sub.remove(sub.size() - 1);
}
}
}
// ------ method2 end --------
public static void main(String[] args) {
String s = "aab";
System.out.println(partition(s));
}
}
复制代码4. 总结
方法一多想想自己还能写出来，方法二确实在不看答案之前想不出来。学习了
可以明显看出构造出一个快捷的回文数表之后，方法二的所需时间比方法一少了。套入现在的开发来说，有些比较追究性能的时候，可以稍微考虑用多一些空间来加快计算的性能。用空间来换时间。这也是一个思路。
不能满足于可以解决，有时候可以有更秀的操作，可以帮我们写出更好的代码。学习他人的长处来充实自己。
本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情
