力扣131.分割回文串
原题，以下是题目描述：
题目会给一个字符串，我们需要找到所有的分割方式，让分割后的所有子字符串都是回文字符串。这题我看讨论区说跟子集那一道题很相似，不过我没看出来🤡🤡🤡，但是这不重要，看不出来就用自己的方式给他做出来就行。
思路
我们需要找到所有的组合，第一想法当然是使用深度优先搜索。我们从第一个字符开始切割，分别判断分割前后的两个字符串是否为回文串。如下文字演示：
我们以题目给出的例子 s="aab" 为例子。
我们首先从第一个字符分割字符串: "a" "ab"
我们判断出 "a" 为回文串，"ab" 不是，并且 "ab" 的长度是大于 1 的，我们将 "ab" 送入下一次递归内。
下一次递归 s="ab"
继续从第一个字符开始分割: "a" "b"
这里两个字符都为回文串，且 后一个串的长度 为 1 ，我们将这个路径加入结果内: "a" "a" "b"
然后回到第一个递归内，也就是 s="aab"
然后我们从第二个字符开始分割: "aa" "b"
判断，"aa" 为回文串，"b" 为回文且长度为 1 ，我们也将这个路径加入结果: "aa" "b"
继续分割: "aab" ""
"aab"不为回文串，""为空，所以已经分割完了，可以直接返回结果了
整个结果是:
[ ["a" "a" "b"] ["aa" "b"] ]
以上是具体思路，当然，各种边界条件需要额外处理。
代码一
我们首先直接使用上述的思路来一版粗糙的，能过的代码：
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = partition2(s);
if (isPalindromic(s)&&s.length()>1){
ArrayList<String> l=new ArrayList<>();
l.add(s);
res.add(l);
}
return res;
}
public List<List<String>> partition2(String s) {
int len=s.length();
ArrayList<List<String>> res=new ArrayList<>();
for (int i = 0; i < len; i++) {
String s1=s.substring(0,i+1);
String s2=s.substring(i+1,len);
ArrayList<String> l=new ArrayList<>();
if (s2.isEmpty()){
if (i==0){
l.add(s);
res.add(l);
return res;
}
continue;
}
if(!isPalindromic(s1)){
continue;
}
if (isPalindromic(s2)){
l.add(s1);
l.add(s2);
res.add(l);
}
if (s2.length()>1){
List<List<String>> lists = partition2(s2);
for (List<String> list : lists) {
list.add(0,s1);
}
res.addAll(lists);
}
}
return res;
}
public boolean isPalindromic(String s){
byte[] array = s.getBytes();
int len=array.length;
int left=0,right=len-1;
while (left<right){
if (array[left++]!=array[right--]){
return false;
}
}
return true;
}
}
代码比较容易理解，原原本本的按照思路所写。但是很明显这版代码是很慢的，因为肉眼可见还有许多可以优化的地方，我们一个个看：
优化思路
- 首先，我们使用的是回溯添加，我们将现在的s1串遍历插入到下一步返回的结果内。第一点是我们每个递归内都需要创建一个 res 列表，然后我们在添加的时候选择的是插入到最前，这也非常耗时，因为我们使用的是ArrayList，插入时需要后面的值移动。这里我们怎么优化？我们可以使用一个路径列表记录前面的所有路径，然后在满足要求后直接添加到结果列表里。这样我们避免了 res 列表，也不需要头插。也不用返回值。
- 这里isPalindromic函数我脑子抽了，使用的是getByte，实际测试下来，直接使用 charAt 函数更快。
- 这里的循环长度是 len，但是我们判断了 s2 串为空串时直接 continue ，完全没必要，我们直接循环 len-1 次即可。还可以将判断去除。
- 对于 s1 串的回文判断其实可以直接提前到 s1 获取后，这样也省去了很多额外操作。
代码二
我们优化了上述说法，再额外优化了一点边界判断后的代码长这样：
class Solution {
private final ArrayList<List<String>> partitionRes = new ArrayList<>();
public List<List<String>> partition(String s) {
if (isPalindromic(s)) {
ArrayList<String> l = new ArrayList<>();
l.add(s);
partitionRes.add(l);
if (s.length()==1){
return partitionRes;
}
}
partition2(s, new ArrayList<>());
return partitionRes;
}
public void partition2(String s, ArrayList<String> path) {
int len = s.length();
for (int i = 0; i < len-1; i++) {
String s1 = s.substring(0, i + 1);
if (!isPalindromic(s1)) {
continue;
}
String s2 = s.substring(i + 1, len);
ArrayList<String> l = new ArrayList<>(path);
l.add(s1);
if (s2.length() > 1) {
partition2(s2, l);
}
if (isPalindromic(s2)) {
l.add(s2);
partitionRes.add(l);
}
}
}
public boolean isPalindromic(String s){
int left=0,right=s.length()-1;
while (left<right){
if (s.charAt(left++)!=s.charAt(right--)){
return false;
}
}
return true;
}
}
优化后的代码表现还算优秀，打败百分之99.9。时间复杂度在O(n\times 2n)。
力扣131.分割回文串
https://www.than.pw/archives/019c7f5b-795d-73fc-a119-717aabc18df2