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

示例 1：

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

示例 2：

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

解题思路

动态规划 + 回溯。先用动态规划把所有可能的子串是否为回文串预判断出来，然后用回溯搜索所有可能的分割方案。

动态规划（预处理回文判断）：

• 回溯过程会频繁查询各种子串是否为回文串。为了将查询时间降至 $O(1)$，可以先构建一个二维boolean数组 $dp$。
• 定义 $dp[i][j]$ 为 true 表示字符串从索引 $i$ 到 $j$ 的子串是回文串。
• 状态转移分析：当 $s[i] == s[j]$ 时，子串是否为回文取决于它的内部子串 $s[i+1 \dots j-1]$ 是否为回文。如果 $j - i \le 2$（例如 a、aa、aba），则直接是回文串。
• 状态转移方程：dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i+1][j-1])

回溯搜索（穷举分割方案）：

• 定义：递归函数 dfs(startIndex)，表示当前正在处理字符串从 startIndex 开始的剩余部分。
• 终止条件：如果 startIndex 已经到达字符串的末尾，说明整个字符串已经被完全合法地分割，此时将当前的分割路径加入到结果集中。
• 单层搜索逻辑：在当前层，通过循环指针 $i$ 从 startIndex 遍历到字符串末尾，尝试截取子串 $s[\text{startIndex} \dots i]$。
• 判断与递归：查询 $dp[\text{startIndex}][i]$
  • 如果是回文串，就将该子串加入路径记录中，接着递归调用 dfs(i + 1) 切割剩余部分
  • 如果不是，则直接跳过，继续尝试更长的截取方式。
• 回溯：递归返回后，将刚刚加入的子串从路径记录中移除，以便尝试下一种分割方案。

Java实现

class Solution {
    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    boolean[][] dp;
    public List<List<String>> partition(String s) {
        int n = s.length();
        dp = new boolean[n][n];

        // 1. 先用动态规划把所有可能的子串是否为回文串预判断出来
        for (int i = n-1; i >= 0; i--){
            for (int j = i; j < n; j++){
                if (s.charAt(i) == s.charAt(j) && (j-i <= 2 || dp[i+1][j-1])){
                    dp[i][j] = true;
                }
            }
        }
        // 2. 回溯
        dfs(s,0);
        return result;
    }

    private void dfs(String s, int startIndex){
        if(startIndex >= s.length()){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++){
            if (dp[startIndex][i]){
                path.add(s.substring(startIndex, i+1));
                dfs(s, i+1);
                path.remove(path.size()-1);
            }
        }
    }
}