[leetcode]131.分割回文串
题目
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = “aab” 输出：[[“a”,”a”,”b”],[“aa”,”b”]]
示例 2：
输入：s = “a” 输出：[[“a”]]
提示：
1 <= s.length <= 16 s 仅由小写英文字母组成
解题思路
我的思路
首先本题至少有一个回文串，可以大体划分为两部分。第一部分是每个遍历每个元素。第二部分是判断回文串。
遍历不用多数，走一遍放在数组里就行。
判断回文串可以通过栈来进行匹配。
其他思路
回溯 + 动态规划预处理（leetcode官方）
由于需要求出字符串 s的所有分割方案，因此我们考虑使用搜索 + 回溯的方法枚举所有可能的分割方法并进行判断。
假设我们当前搜索到字符串的第 ii 个字符，且 s[0..i-1]s[0..i−1] 位置的所有字符已经被分割成若干个回文串，并且分割结果被放入了答案数组 \textit{ans}ans 中，那么我们就需要枚举下一个回文串的右边界 jj，使得 s[i..j]s[i..j] 是一个回文串。
因此，我们可以从 ii 开始，从小到大依次枚举 jj。对于当前枚举的 jj 值，我们使用双指针的方法判断 s[i..j]s[i..j] 是否为回文串：如果 s[i..j]s[i..j] 是回文串，那么就将其加入答案数组 \textit{ans}ans 中，并以 j+1j+1 作为新的 ii 进行下一层搜索，并在未来的回溯时将 s[i..j]s[i..j] 从 \textit{ans}ans 中移除。
如果我们已经搜索完了字符串的最后一个字符，那么就找到了一种满足要求的分割方法。
