题目

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

回文串是正着读和反着读都一样的字符串。

示例 1：

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

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

思路

我们来分析一下切割，其实切割问题类似组合问题。
例如对于字符串abcdef：

组合问题：选取一个 a 之后，在bcdef 中再去选取第二个，选取 b 之后在 cdef 中在选取第三个…..，直到无可选元素为止。
切割问题：切割一个 a 之后，在 bcdef 中再去切割第二段，切割 b 之后在 cdef 中在切割第三段…..，直到无可选元素为止。

感受出来了不？

只不过本题题目规定每个子串都得是回文串，也就说在本题中，切割的区间（选取元素）是有约束条件的。

所以切割问题，同样也可以抽象为一颗树形结构，如图：

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

回溯三部曲

1、函数参数

全局变量字符串 s 存放题目输入的 s ，方便下面使用。

全局变量数组 path 存放切割后回文的子串，二维数组 result 存放结果集。（这两个参数可以放到函数参数里）。

本题递归函数参数还需要 startIndex ，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。

在 39. 组合总和我们深入探讨了组合问题什么时候需要 startIndex，什么时候不需要startIndex。

代码如下：

String s = null;
List<List<String>> result = new ArrayList<>();
LinkedList<String> path = new LinkedList<>();
void backtracking(int startIndex) {

2、递归函数终止条件

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

那么在代码里什么是切割线呢？

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

所以终止条件代码如下：

void backtracking(int startIndex) {
        // 终止条件
        if (startIndex >= s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }

3、单层搜索的逻辑

来看看在递归循环，中如何截取子串呢？

在 for (int i = startIndex; i < s.length(); i++) 循环中，我们定义了起始位置 startIndex ，那么 [startIndex, i] 就是要截取的子串。

首先判断这个子串是不是回文，如果是回文，就加入在 LinkedList<String> path 中，path 用来记录切割过的回文子串。

代码如下：

for (int i = startIndex; i < s.length(); i++) {
    if (isPalindrome(startIndex, i)) {  // 是回文子串
        String tmp = s.substring(startIndex, i + 1);  // 获取[startIndex,i] 在 s 中的子串
        path.add(tmp);
    } else { // 如果不是则直接跳过
        continue;
    }

    backtracking(i + 1); // 寻找i+1为起始位置的子串
    path.removeLast();   // 回溯过程，弹出本次已经填在的子串
}

注意切割过的位置，不能重复切割，所以传入下一层的起始位置为 i + 1，即 backtracking(i + 1)。

判断回文子串

最后我们看一下回文子串要如何判断了，判断一个字符串是否是回文。

可以使用双指针法，一个指针从前向后，一个指针从后先前，如果前后指针所指向的元素是相等的，就是回文字符串了。

那么判断回文的 Java 代码如下：

boolean isPalindrome(int left, int right) {
    while (left <= right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }

        left++;
        right--;
    }

    return true;
}

补充说明：题目输入的字符串 s 已经存入全局变量 s，所以可以直接使用。

根据回溯法的模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

所以不难写出答案

总结

这道题目在 leetcode 上是中等，但可以说是 hard 的题目了，但是代码其实就是按照模板的样子来的。

那么难究竟难在什么地方呢？

我列出如下几个难点：

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

我们平时在做难题的时候，总结出来难究竟难在哪里也是一种需要锻炼的能力。

一些同学可能遇到题目比较难，但是不知道题目难在哪里，反正就是很难。其实这样还是思维不够清晰，这种总结的能力需要多接触多锻炼。

本题我相信很多同学主要卡在了第一个难点上：就是不知道如何切割，甚至知道要用回溯法，也不知道如何用。也就是没有体会到按照求组合问题的套路就可以解决切割。

如果意识到这一点，算是重大突破了。接下来就可以对着模板照葫芦画瓢。

但接下来如何模拟切割线，如何终止，如何截取子串，其实都不好想，最后判断回文算是最简单的了。

关于模拟切割线，其实就是 index 是上一层已经确定了的分割线，i 是这一层试图寻找的新分割线

除了这些难点，本题还有细节，例如：切割过的地方不能重复切割所以递归函数需要传入i + 1。

所以本题应该是一个道hard题目了。

答案

Java

class Solution {
    String s = null; // 题目提供的字符串 s ，存储在全局变量，方便使用

    List<List<String>> result = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();  // 放已经回文的子串

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

    void backtracking(int startIndex) {
        // 终止条件
        if (startIndex >= s.length()) {
            // 如果起始位置已经大于 s 的大小，说明已经找到了一组分割方案了
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            // 判断是否为回文
            if (isPalindrome(startIndex, i)) {  // 是回文子串
                // 获取 [startIndex,i] 在 s 中的子串
                String tmp = s.substring(startIndex, i + 1);
                path.add(tmp);
            } else {  // 不是回文，跳过
                continue;
            }

            backtracking(i + 1);  // 寻找i+1为起始位置的子串
            path.removeLast();  // 回溯过程，弹出本次已经填在的子串
        }
    }

    // 判断字符串 s[left,right] 区间内的字符是否构成回文
    boolean isPalindrome(int left, int right) {
        while (left <= right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}

REF

https://programmercarl.com/0131.分割回文串.html
https://leetcode-cn.com/problems/palindrome-partitioning/

算法总纲

131. 分割回文串

题目

思路