🥈131. 分割回文串

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

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

示例 1：

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

示例 2：

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

提示：

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

题解

看到这种题还是一脸懵逼(´⊙ω⊙`)！

回溯

假设现在搜索到了字符串中第个字符，且第位置的所有字符都已经被分割成了若干回文串，且分割结果已经放入结果数组中，那么就需要枚举下一个回文串的右边界，使得是一个回文串。

因此，可以从开始，从小到大枚举。对于当前枚举的，可以用双指针判断是否为回文串，如果是，就加入结果数组中，并将作为新的进行下一轮搜索，并在未来回溯时将从中删除。

如果已经搜完最后一个字符，那么就找到了满足条件的分割方式。

code

看题解一下子看明白了，但是写起来还是无从下手！可以先看一下回溯的模板：
♻️ 回溯法

res = []
path = []

def backtrack(未探索区域, res, path):
    if 未探索区域满足结束条件:
        res.add(path) # 深度拷贝
        return
    for 选择 in 未探索区域当前可能的选择:
        if 当前选择符合要求:
            path.add(当前选择)
            backtrack(新的未探索区域, res, path)
            path.pop()

按照模板，

• 未探索区域：剩余未搜索的字符串s
• 结束条件：s为空
• 未探索区域当前可能的选择：每次选择可以选取s的1到s.length，
• 当前选择符合要求：cur是回文字符串
• 新的未探索区域：s去除cur的剩余字符串，

所以代码如下

回溯+动态规划

回溯已经在上面说清楚了，现在需要把判断回文串进行优化！

动态规划

判断是否为回文串时，常规方法是使用双指针分别指向和，然后每次判断两个指针指向的字符是否相同，直至两个指针相遇。但这样会出现重复计算。例如：

当 时，对于前 2 个字符 aa，有 2 种分割方法[aa] 和[a,a]，当我们每一次搜索到字符串的第 i=2 个字符 b 时，都需要对于每个 s[i..j] 使用双指针判断其是否为回文串，这就产生了重复计算。

所以，可以将字符串s每一个子串是否为回文串预处理出来，使用动态规划即可。设表示是否为回文串，状态转移方程为：

其中表示与运算，即为回文串，当且仅当s为空字符串，或s长度为1，或首尾字母相同且为回文串.

预处理之后，只需时间就可以判断是否为回文串。