【LeetCode 热题 100】131. 分割回文串——回溯

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

整体思路

这段代码旨在解决一个经典的组合搜索问题：分割回文串 (Palindrome Partitioning)。其目标是找到一个字符串 s 的所有可能的分割方案，使得每个分割出的子串都是一个回文串。

该算法采用 深度优先搜索（DFS） 配合 回溯（Backtracking） 的策略来系统地探索所有可能的分割点。这个特定实现的DFS逻辑稍显独特，但其核心思想是，在字符串的每个位置 i，决定是否在此处进行“切割”。

1. DFS 状态定义：

   • 核心的 dfs(i, start, ...) 函数通过两个索引来定义其状态：
     • i: 代表当前正在考虑的子串的右边界。
     • start: 代表当前正在构建的子串的左边界。
   • 因此，s.substring(start, i+1) 是当前正在被评估是否为回文串的候选子串。

2. 递归中的决策（二分选择）：

   • 在 dfs 的每一步（由 i 定义），算法实际上做出了两种选择：
     • a. 选择不切割：dfs(i + 1, start, ...)。这个递归调用意味着我们决定不在 i 位置结束当前子串。我们把右边界 i 向右移动到 i+1，而左边界 start 保持不变，相当于延长了当前的候选子串，继续向后探索。
     • b. 选择切割（如果满足条件）：if (isPalindrome(s, start, i)) { ... }。这个分支代表了在 i 位置结束当前子串的决定。
       • 条件：只有当 s.substring(start, i+1) 是一个回文串时，这个选择才是有效的。
       • 执行：如果条件满足，就将这个回文子串加入到当前的路径 path 中。然后，发起一个新的 dfs 调用 dfs(i + 1, i + 1, ...)，从 i+1 位置开始寻找下一个回文子串（注意 start 被更新为 i+1）。
       • 回溯：在从“切割”分支的递归调用返回后，必须执行 path.removeLast()，撤销刚才的切割决定。这使得程序可以回溯到上一个状态，并继续探索其他可能性（例如，不在此处切割，而是构成一个更长的回文串）。

3. 基准情况与结果收集：

   • 当 i 到达字符串的末尾（i == n）时，意味着整个字符串已经被成功地分割成了一系列子串（存储在path中）。此时，一个完整的有效分割方案被找到，将其复制一份并加入到最终的结果列表 ans 中。

通过这种方式，算法不重不漏地枚举了所有可能的、由回文串构成的分割方案。

完整代码

class Solution {
    /**
     * 找到字符串 s 的所有回文分割方案。
     * @param s 输入的字符串
     * @return 一个包含所有可能分割方案的列表
     */
    public List<List<String>> partition(String s) {
        // ans: 存储所有有效的分割方案
        List<List<String>> ans = new ArrayList<>();
        // path: 在DFS过程中，存储当前正在构建的单个分割方案
        List<String> path = new ArrayList<>();
        // 从索引 0 开始进行深度优先搜索
        dfs(0, 0, ans, path, s);
        return ans;
    }

    /**
     * 深度优先搜索辅助函数。
     * @param i      当前考虑的子串的右边界
     * @param start  当前考虑的子串的左边界
     * @param ans    最终结果列表
     * @param path   当前路径（一个分割方案）
     * @param s      原始字符串
     */
    private void dfs(int i, int start, List<List<String>> ans, List<String> path, String s) {
        int n = s.length();
        // 基准情况：如果 i 到达了字符串末尾，说明整个字符串已被成功分割
        if (i == n) {
            // 将当前有效的路径复制一份，添加到结果集中
            ans.add(new ArrayList<>(path));
            return;
        }

        // --- 决策 1: 不在 i 位置切割 ---
        // 如果 i 还不是最后一个字符，可以继续向后延伸当前的子串
        if (i < n - 1) {
            // 递归调用，右边界 i 移动到 i+1，左边界 start 保持不变
            dfs(i + 1, start, ans, path, s);
        }

        // --- 决策 2: 在 i 位置切割（如果 s[start...i] 是回文串）---
        if (isPalindrome(s, start, i)) {
            // 将找到的回文子串加入当前路径
            path.add(s.substring(start, i + 1));
            // 从 i+1 开始，寻找下一个子串 (新的 start 变为 i+1)
            dfs(i + 1, i + 1, ans, path, s);
            // 【回溯】: 撤销刚才的选择，将子串从路径中移除，以便探索其他可能性
            path.removeLast();
        }
    }

    /**
     * 辅助函数：判断字符串 s 的子串 s[l...r] 是否为回文串。
     * @param s 原始字符串
     * @param l 子串的左边界（包含）
     * @param r 子串的右边界（包含）
     * @return 如果是回文串，返回 true；否则，返回 false。
     */
    private boolean isPalindrome(String s, int l, int r) {
        // 使用双指针法进行判断
        while (l < r) {
            if (s.charAt(l++) != s.charAt(r--)) {
                return false;
            }
        }
        return true;
    }
}

时空复杂度

时间复杂度：O(N * 2^N)

1. 递归树的大小：在最坏的情况下（例如，字符串 s = "aaaaa"），几乎每个子串都是回文串。在字符串的每个字符之间，我们都有“切割”或“不切割”两种选择。这会产生一个大小约为 2^(N-1) 的递归树。因此，DFS调用的总次数是指数级的，大致为 O(2^N)。
2. 每个节点的工作量：在 dfs 函数的每次调用中，都会执行 isPalindrome 检查和可能的 s.substring 操作。
   • isPalindrome(s, l, r) 的时间复杂度是 O(r-l)，最坏情况下是 O(N)。
   • s.substring(...) 在Java中也会创建一个新字符串，时间复杂度也是 O(N)。
3. 综合分析：
   • 总的时间复杂度是递归树的节点数乘以每个节点的工作量。
   • 因此，一个较为宽松但被广泛接受的上限是 O(N * 2^N)。

空间复杂度：O(N)

1. 主要存储开销：算法的额外空间开销主要来自两个方面：递归调用栈的深度和存储路径的 path 列表。
2. 递归栈深度：递归的最大深度发生在我们将字符串分割成 N 个单字符子串时（例如 s="abc" -> ["a", "b", "c"]）。在这种情况下，递归栈的深度为 N。
3. path 列表空间：path 列表存储了当前的分割方案。在最坏的情况下，它也会存储 N 个单字符子串，总长度为 N。
4. ans 列表：存储最终结果的空间不计入额外辅助空间复杂度，但其大小本身也可能是指数级的。

综合分析：
递归栈和 path 列表的空间占用都与输入字符串的长度 N 成线性关系。因此，算法的额外辅助空间复杂度为 O(N)。

参考灵神