问题

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案
回文串是正着读和反着读都一样的字符串

示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：
输入：s = "a"
输出：[["a"]]

思路

本题涉及到两个关键问题：

  • 切割问题，有不同的切割方式
  • 判断回文

这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯

那么回溯究竟是如果切割字符串呢
我们来分析一下切割，其实切割问题类似组合问题

例如对于字符串abcdef：

  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选取第三个…..
  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…..

所以切割问题，也可以抽象为一颗树形结构，如图：
leetcode-131：分割回文串 - 图1
递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法
此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的

回溯三部曲

  • 递归函数参数

    • 全局变量数组path存放切割后回文的子串，二维数组result存放结果集。（这两个参数可以放到函数参数里）
    • 本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的
      1. List<List<String>> result = new ArrayList<Integer>();
      2. List<String> path = new ArrayList<String>(); // 放已经回文的子串
      3. public void backtracking (String s, int startIndex) {

  • 递归函数终止条件

leetcode-131：分割回文串 - 图2

  • 从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止终止条件

那么在代码里什么是切割线呢？
在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线

public void backtracking (String s, int startIndex) {
    // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
    if (startIndex >= s.length()) {
        result.add(new ArrayList<String>(path));
        return;
    }
}
  • 单层搜索的逻辑
    • 来看看在递归循环，中如何截取子串呢？
      • 在for (int i = startIndex; i < s.size(); i++)循环中，我们定义了起始位置startIndex，那么[startIndex, i] 就是要截取的子串
      • 首先判断这个子串是不是回文，如果是回文，就加入在path中，path用来记录切割过的回文子串 ```java for (int i = startIndex; i < s.length(); i++) { if (isPalindrome(s, startIndex, i)) { // 是回文子串 // 获取[startIndex,i]在s中的子串 string str = s.substring(startIndex, i + 1); path.add(str); } else { // 如果不是则直接跳过 continue; } backtracking(s, i + 1); // 寻找i+1为起始位置的子串 path.remove(path.size() - 1); // 回溯过程，弹出本次已经填在的子串 }
**注意切割过的位置，不能重复切割，所以，**`**backtracking(s, i + 1)**`**; 传入下一层的起始位置为**`**i + 1**`

<a name="uM2ak"></a>
## 判断回文子串
最后我们看一下回文子串要如何判断了，判断一个字符串是否是回文<br />可以使用**双指针法**，一个指针从前向后，一个指针从后先前，如果前后指针所指向的元素是相等的，就是回文字符串了
```java
 bool isPalindrome(String s, int start, int end) {
     char[] str = s.toCharArray();
     for (int i = start, j = end; i < j; i++, j--) {
         if (char[i] != char[j]) {
             return false;
         }
     }
     return true;
 }

class Solution {

    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<String>(); 

    public void backtracking (String s, int startIndex) {

        if (startIndex >= s.length()) {
            result.add(new ArrayList<String>(path));
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s, startIndex, i)) { 

                String str = s.substring(startIndex, i + 1);
                path.add(str);
            } else {               
                continue;
            }
            backtracking(s, i + 1); 
            path.remove(path.size() - 1);        
        }
    }

    public boolean isPalindrome(String s, int start, int end) {
        char[] str = s.toCharArray();
        for (int i = start, j = end; i < j; i++, j--) {
            if (str[i] != str[j]) {
                return false;
            }
        }
        return true;
        }

    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return result;
    }
}

ArrayList<String> cannot be convert to List<List<String>>

难点

  • 切割问题可以抽象为组合问题
  • 如何模拟那些切割线
  • 切割问题中递归如何终止
  • 在递归循环中如何截取子串
  • 如何判断回文