131.分割回文串

目标

给你一个字符串 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。