题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：
输入：s = “a”
输出：[[“a”]]
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成
解题思路
字符串的分割方案F(s)是一个可以拆分为子问题的问题，我们设原字符串的长度为n, 考查以当前位置i为起始点的字符串s[i][n]， 对应的分割方案结果集为F(s[i][n])，若子字符串s[i][j]是回文串，那么原问题的一个子集可以表示为 {s[i][j] , s[j][n] }.
基于以上思路，我们需要知道字符串 s的所有子字符串的头尾位置，依据这个信息可以加速我们的动态规划过程。
记 s的子字符串的头尾位置i，j是否满足回文串为函数 f[i][j],
f[i][j] = f[i+1][j-1] s.charAt(i) = s.charAt(j)
= false
所以求字符串 s的所有子字符串，这个过程也是一个动态规划，求解 f[i][j] 的时候，为了利用上前置已求得的答案，注意i是递减的， j是递增的
代码实现
import java.util.ArrayList;
import java.util.List;public class Leetcode131 {public static void main(String[] args) {String s = "abbab";System.out.println(partition(s));}public static List<List<String>> partition(String s) {List<List<String>> r = new ArrayList<>();boolean[][] huiwen = new boolean[s.length()][s.length()];for (int i = 0; i < s.length(); i++) {huiwen[i][i] = true;}for (int i = s.length() - 1; i >= 0; i--) {for (int j = i + 1; j < s.length(); j++) {if (s.charAt(i) == s.charAt(j)) {huiwen[i][j] = (j - i == 1) ? true : huiwen[i + 1][j - 1];}}}dfs34(s, 0, r, new ArrayList<>(), huiwen);return r;}private static void dfs34(String s, int i, List<List<String>> r, List<String> t, boolean[][] huiwen) {if (i == s.length()) {r.add(new ArrayList<>(t));return;}for (int j = i; j < s.length(); j++) {if (huiwen[i][j] == true) {t.add(s.substring(i, j + 1));dfs34(s, j + 1, r, t, huiwen);t.remove(t.size() - 1); }}}
}