目标
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]示例 2：
输入：s = "a"
输出：[["a"]]说明：
- 1 <= s.length <= 16
- s 仅由小写英文字母组成
思路
返回将字符串划分为回文子串的所有可能方案。
定义 dp[i] 表示将前 i + 1 个字符划分为回文子串的所有可能方案。dp[i] 可以取 dp[i - 1] 每种方案的最后一或两个回文，判断能否与当前字符合并成新的回文。
代码
/**
* @date 2025-03-01 20:16
*/
public class Partition131 {
public List<List<String>> partition(String s) {
int n = s.length();
List<List<String>>[] dp = new List[n];
for (int i = 0; i < n; i++) {
dp[i] = new ArrayList<>();
}
char[] chars = s.toCharArray();
dp[0].add(new ArrayList<>());
dp[0].get(0).add((String.valueOf(chars[0])));
for (int i = 1; i < n; i++) {
dp[i] = new ArrayList<>();
for (List<String> list : dp[i - 1]) {
// 首先将单个字符加入
List<String> tmp = new ArrayList<>(list);
tmp.add(String.valueOf(chars[i]));
dp[i].add(tmp);
String cur = String.valueOf(chars[i]);
// 判断能与最后一个回文合并成新的回文
if (list.get(list.size() - 1).equals(cur)) {
tmp = new ArrayList<>(list.subList(0, list.size() - 1));
tmp.add(list.get(list.size() - 1) + cur);
dp[i].add(tmp);
}
// 判断能否与后两个回文合并成新的回文
if (list.size() > 1 && list.get(list.size() - 2).equals(cur)) {
tmp = new ArrayList<>(list.subList(0, list.size() - 2));
tmp.add(list.get(list.size() - 2) + list.get(list.size() - 1) + cur);
dp[i].add(tmp);
}
}
}
return dp[n - 1];
}
}
性能
时间复杂度 O(n * 2^n)，假设每个字符之间都有一个逗号，考虑选或不选共有 2^(n - 1) 种划分。前 i + 1 个 字符有 2^i 种划分， 等比数列求和得到 2^n - 1。
