当前位置：首页 > news >正文

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

news 2025/7/27 9:38:46

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

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N * 2^N)
- 空间复杂度：O(N)

整体思路

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

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

DFS 状态定义：
- 核心的 dfs(i, start, ...) 函数通过两个索引来定义其状态：
  - i: 代表当前正在考虑的子串的右边界。
  - start: 代表当前正在构建的子串的左边界。
- 因此，s.substring(start, i+1) 是当前正在被评估是否为回文串的候选子串。
递归中的决策（二分选择）：
- 在 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()，撤销刚才的切割决定。这使得程序可以回溯到上一个状态，并继续探索其他可能性（例如，不在此处切割，而是构成一个更长的回文串）。
基准情况与结果收集：
- 当 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)

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

空间复杂度：O(N)

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