本题采用回溯搜索与双指针回文剪枝算法又称“决策树切分路径搜索法”解决字符串全回文分割方案穷举问题。其核心本质是将一维字符串的分割边界决策转化为多叉决策树的深度优先搜索DFS回溯并在分支生成阶段利用双指针即时进行回文强剪枝。当前提供的源码实现了在最坏时间复杂度 O(n * 2^n) 和额外空间复杂度 O(n)其中 n 为字符串长度条件下的全局可行解检索最终走向是精准输出所有满足子串均为回文串的组合方案。一、 问题本质与数据模型对于给定的字符串 s题目要求将其分割成若干个子串且每个子串都必须是回文串。该问题在决策上面临的核心约束与物理特性如下动态边界划分约束设当前待处理子串的左边界起点为 i。我们可以在区间 [i, n-1] 中选择任意位置 j 作为当前切分点的终点从而将字符串切割为两部分左侧候选子串 s[i...j] 与右侧未处理后缀 s[j1...n-1]。回文先验剪枝机制一个切分方案要成为最终的合法答案当前切分的局部子串 s[i...j] 必须是回文串。如果 s[i...j] 本身不满足回文定义则其右侧子树代表的后续所有组合方案物理上均不可能成立。为了高效穷举算法引入了“回溯与强剪枝模型”。算法维护一个动态增长的单条决策路径栈path。在每一个决策深度 i循环步进地尝试不同的右切分边界 j。每当双指针判定局部子串 s[i...j] 满足回文要求时才将该子串压入path并递归深入至下一阶段j 1一旦不满足则放弃进入该深度的子决策分支实现即时剪枝。当 i 成功步进到字符串末尾 n 时说明整条路径上的切分均合法拷贝当前路径栈副本加入全局结果容器。二、 算法演进对比在解决回文串分割重构问题时回溯搜索配合即时剪枝在空间与时间性能上表现极其均衡解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷全组合暴力生成 过滤O(n * 2^n)O(2^n * n)穷举字符串的所有切分方案共有 2^(n-1) 种可能在收集到完整路径后再逐个过滤非回文方案产生海量无效拓扑分支在无法即时剪枝的情况下浪费大量算力和临时存储空间回溯搜索 动态规划预处理O(2^n)O(n^2)提前使用二维 DP 状态表存储所有子串的回文特性回溯时以 O(1) 的时间检索剪枝条件需要额外的 O(n^2) 空间来存储 DP 状态矩阵小规模数据下空间开销相对较大回溯搜索 双指针即时核验当前解法O(n * 2^n)O(n)深度优先搜索驱动状态演进分支生成时利用双指针现场进行回文判定并即时剪枝每一个有效切分点都需要现场执行双指针向中心靠拢的线性扫描存在一定的重复字符比较开销三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于回溯框架内的深度优先搜索和judge辅助核验器其内部决策分支证明如下1. 递归基准终止分支if (i s.length())执行ans.add(new ArrayList(path));物理意义指针 i 成功步进到字符串最右侧边界表明全字符串的分割边界判定顺利通过。此时当前的path中所有的物理截取片段都被判定为合法的回文串。因此拷贝当前路径栈副本并载入结果集ans中。2. 决策树多叉分支循环for (int j i; j s.length(); j)执行遍历可能作为分割终点的索引 j。物理意义代表当前在索引 i 处有多个可能的分割落点。每一个 j 都对应决策树中的一棵子树分支。3. 双指针即时强剪枝if (judge(s.toCharArray(), i, j))执行验证子串 s[i...j] 是否为回文。如果是则推进决策path.add 递归若不是则跳过该子树。数学证明如果当前局部片段 s[i...j] 本身就不是回文串那么任何基于该切分点继续向下切分所产生的所有子方案都绝对不可能满足“所有子串都是回文串”的要求。因此该分支所统辖的子树应当被直接在物理上切除极大地收窄了搜索树的空间。4. 回溯状态恢复path.removeLast();执行弹出路径栈中的最新片段。物理意义通过深度优先搜索的多叉树探索完某个子分支后需要将状态还原确保同一层级的后续兄弟分支如扩大 j 范围的下一个切分点在共享的path容器中拥有干净的拓扑状态。四、 算法执行状态机步进示例以输入s aab为例规模 n 3展示回溯搜索与剪枝状态机的演进全貌步骤递归深度 i当前循环边界 j当前切分片段是否回文 / 状态判定物理剪枝与状态更新动作全局路径栈 path 状态初始0---激活 DFS(0)[ ]100a是推进path.add(a)激活 DFS(1)[ a ]211a是推进path.add(a)激活 DFS(2)[ a, a ]322b是推进path.add(b)激活 DFS(3)[ a, a, b ]43--递归基准命中捕获可行解ans 载入副本回溯弹出 b[ a, a ]512ab否触发违规剪枝跳过当前递归分支[ a, a ]6----DFS(1) 循环完结回溯弹出 a[ a ]701aa是推进path.add(aa)激活 DFS(2)[ aa ]822b是推进path.add(b)激活 DFS(3)[ aa, b ]93--递归基准命中捕获可行解ans 载入副本回溯弹出 b[ aa ]10----DFS(2) 循环完结回溯弹出 aa[ ]1102aab否触发违规剪枝跳过当前递归分支[ ]终止----全局 DFS 运行结束输出结果集最终输出 2 组方案五、 源码实现import java.util.ArrayList; import java.util.List; class Solution { public ListListString partition(String s) { // 初始化全局可行解结果容器 ListListString ans new ArrayList(); // 动态路径栈记录当前深度优先搜索决策分支中已选定的回文片段 ListString path new ArrayList(); // 从字符串第 0 位开始启动回溯搜索状态机 dfs(ans, path, s, 0); return ans; } private void dfs(ListListString ans, ListString path, String s, int i) { // 基准收敛条件若指针 i 已经移动至字符串最右边界说明已成功找到一条合法的完整分割链条 if (i s.length()) { ans.add(new ArrayList(path)); // 拷贝当前路径副本写入结果集 return; } // 决策分支循环遍历当前可供切分的所有右边界终点 j for (int j i; j s.length(); j) { // 回文即时剪枝调用辅助核验器检验当前局部子串 s[i...j] 的回文特性 if (judge(s.toCharArray(), i, j)) { // 状态推进若满足回文性质截取子串并压入路径栈中 path.add(s.substring(i, j 1)); // 分治递归指针步进至 j 1向下一决策深度进发 dfs(ans, path, s, j 1); // 状态回溯撤销当前选择弹出栈顶元素为尝试更宽的右切分边界j 自增清理现场 path.removeLast(); } } } // 辅助核验器双指针中心回缩判定 private boolean judge(char[] ch, int i, int j) { // 维持对称性校验双向指针靠拢 while (i j) { if (ch[i] ! ch[j]) { return false; // 任意对称字符不相等立即拦截判定无效 } i; j--; } return true; // 通过全部核验判定为合法回文片段 } }六、 复杂度分析1. 时间复杂度O(n * 2^n)分析在最坏情况下例如输入字符串由全相同字符组成如 aaaa字符串的每一个位置都可以作为一个合法的回文切分落点。此时决策树的总可能切分方案数等于具有 n-1 个可切分空档的二值化判定即 2^(n-1) 种。在回溯树的每一个有效叶子节点及分支树节点中我们调用了judge方法进行双指针常数项级线性扫描核验耗时 O(n)同时通过substring物理截取子串并执行了物理内存拷贝耗时 O(n)。结论算法整体所需的基本计算步数受上限函数 n * 2^n 控制时间复杂度为 O(n * 2^n)。2. 空间复杂度O(n)分析算法在执行期间其额外空间的开销完全由两个物理结构决定一是递归方法调用产生的系统执行栈深度在最深探测路径上该深度最多为 n二是共享的局部路径容器path其最多只能存储 n 个长度不等的子串。这两个结构所需消耗的最大物理空间均与字符串长度 n 呈严格的线性正比关系。结论在不计存储最终结果集 ans 内存开销的前提下算法的额外辅助空间复杂度定性为 O(n)。