131. 分割回文串#

class Solution {
    // 主函数：返回字符串 s 的所有“回文分割”方案
    public List<List<String>> partition(String s) {
        // result：保存所有合法分割结果
        List<List<String>> result = new ArrayList<>();

        // dp[i][j] 表示子串 s[i..j]（含 i、j）是否为回文串
        // 使用该表可将回文判断从 O(len) 降为 O(1) 查询
        boolean[][] dp = new boolean[s.length()][s.length()];

        // 预处理所有子串的回文性质：按长度从短到长填表
        for(int len = 1; len <= s.length(); len++) {
            // i 为子串起点，j 为子串终点
            for(int i = 0; i <= s.length() - len; i++) {
                int j = i + len - 1;

                // 长度为1的子串一定是回文
                if(len == 1) {
                    dp[i][j] = true;
                }

                // 长度为2的子串，两个字符相等即为回文
                else if(len == 2) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                }

                // 长度大于2的子串，首尾字符相等且中间是回文串
                else {
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
                }
            }
        }

        // 从下标 0 开始回溯切割，current 记录当前方案
        backtrack(s, 0, new ArrayList<>(), result, dp);
        // 返回全部分割方案
        return result;
    }

    // 回溯函数：从 start 开始切割字符串，构造后续回文段
    private void backtrack(String s, int start, List<String> current, 
                          List<List<String>> result, boolean[][] dp) {
        // 终止条件：start 到达字符串末尾，说明前面已切分成完整合法方案
        if (start >= s.length()) {
            // 加入 current 的副本，防止回溯时被修改
            result.add(new ArrayList<>(current));
            return;
        }

        // 枚举当前段的结束位置 end，尝试 s[start..end] 作为下一段
        for (int end = start; end < s.length(); end++) {
            // 只有当 s[start..end] 是回文时，才是有效切割
            if (dp[start][end]) {
                // 做选择：把当前回文子串加入方案
                current.add(s.substring(start, end + 1));

                // 递归处理后续剩余部分，从 end + 1 开始
                backtrack(s, end + 1, current, result, dp);

                // 撤销选择（回溯）：移除最后一段，尝试其他 end
                current.remove(current.size() - 1);
            }
        }
    }
}