企业官网建设流程全解析

LeetCode 131 回文分割（Palindrome Partitioning）：回溯 + 双索引递归与 O(n·2^n) 复杂度全解

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇指南以 hints/palindrome-partitioning.md 给出的解题提示为核心骨架，系统讲解 LeetCode 131「分割回文串」的完整解法：从「为什么存在 2^n 种切分」的复杂度直觉出发，逐步推导出双索引回溯（j 为当前子串起点、i 为扩展终点）、按起点枚举的回溯、DP 预计算回文表与纯递归返回式四种实现，并结合本仓库多语言源码逐一印证。读完你将掌握回文分割问题的标准思考路径、可直接运行的代码模板，以及一份能写进面试的复杂度分析。

1. 问题定义与目标复杂度

题目要求：给定字符串s，将s分割成若干子串，使得每一个子串都是回文串，返回所有可能的分割方案。

例如s = "aab"的输出为[["a","a","b"], ["aa","b"]]；s = "a"的输出为[["a"]]。

提示文档在开篇即给出了本问题的推荐复杂度目标：

目标解法应达到O(n * 2^n)时间、O(n)空间，其中n为输入字符串长度。

这一目标直接决定了算法形态：由于答案数量本身是指数级的（见下一节），任何解法的下界都跑不出O(2^n)量级，因此回溯（Backtracking）+ 剪枝就是最匹配的范式——它天然适合枚举所有组合，又通过「只接纳回文子串」完成剪枝。仓库中的 cpp/0131-palindrome-partitioning.cpp 头注释也明确标注了Time: O(n x 2^n)、Space: O(n)，与提示文档完全一致。

2. 为什么有 2^n 种切分：Hint 1 的复杂度直觉

提示文档的 Hint 1 给出了一个关键观察：

对给定字符串，存在2^n 种可能的切分，因为在每个索引处都有两个决策：要么在此处切分并开始一个新的子串，要么不切分继续延伸当前子串。

理解这个结论是理解算法结构的钥匙。想象在字符串的n-1个相邻字符之间放置「切/不切」的决策点：

• 切 → 当前子串结束，从下一位置开启新子串；
• 不切 → 当前子串继续向右延伸。

每个位置两个选择，组合起来恰好构成一棵2^n 规模的决策树。回溯算法本质上就是递归遍历这棵决策树：树的高度为n（字符串被逐字符消费），每一条从根到叶的路径对应一种切分方式（其中「每个子串都是回文」的路径才被采纳进结果）。

因此答案集最坏情况下有O(2^n)个方案，每个方案平均长度O(n)，加上对每个方案做回文校验的开销，总时间复杂度定格在O(n * 2^n)——这正是推荐复杂度目标的时间来源。

3. 双索引回溯（j, i）：对应 Hint 2 与 Hint 3 的核心实现

3.1 指针含义与状态设计

提示文档的 Hint 2 定义了本题最精炼的双指针状态：

• j：当前待构造子串的起始索引；
• i：当前正在迭代扩展的索引（即子串的候选终点）。

每一步迭代中只有两类决策：

1. 暂不切分：保持j不变，把i向右推进一位（dfs(j, i+1)），尝试更长的子串；
2. 切分：当s[j..i]是回文时，把该子串放入临时列表part，随后令j = i + 1开启新的子串，并从新起点继续递归（dfs(i+1, i+1)）。

递归的终止条件（Hint 2 强调）：当j走到字符串末尾时停止——这表示从起点到末尾的每一段都已被成功切分成回文，当前part即为一个合法答案。

3.2 代码模板（Python）

Hint 3 补充了初始化细节：从j = 0, i = 0和一个空的临时列表part出发；到达基础条件时，把part的拷贝加入结果集。据此得到的实现如下：

class Solution: def partition(self, s: str) -> List[List[str]]: res, part = [], [] def dfs(j, i): if i >= len(s): if i == j: # 恰好完整切分完整个字符串 res.append(part.copy()) return if self.isPali(s, j, i): # 决策 2：s[j..i] 是回文 → 切分 part.append(s[j : i + 1]) dfs(i + 1, i + 1) # 新子串从 i+1 开始 part.pop() # 回溯：撤销选择 dfs(j, i + 1) # 决策 1：不切分，继续延伸 dfs(0, 0) return res def isPali(self, s, l, r): while l < r: if s[l] != s[r]: return False l, r = l + 1, r - 1 return True

注意两个容易被忽略的细节：

• 基础条件的双重判断：i >= len(s)时只有i == j才意味着「当前子串恰好延伸到末尾且被完整消费」，此时part才是合法答案；若i > j，说明最后一串尚未确定是否为回文，直接返回不收集。
• 回文判定isPali用双指针向中间收缩：l与r一旦出现字符不等立即返回False，最坏O(n)，这是 Hint 2 中明确要求的校验方式。

3.3 该写法的复杂度

• 时间：O(n * 2^n)—— 枚举全部切分组合，每层做O(n)的回文校验；
• 空间：O(n)额外空间（递归栈深度 +part列表），不包含答案输出本身占用的O(n * 2^n)。

与 articles/palindrome-partitioning.md 中「Backtracking - I」一节的结论完全一致。

4. 按起点枚举的回溯：仓库源码的权威实现

除双索引写法外，更常见、也更贴近本仓库实际提交的是按起点枚举的回溯：定义dfs(i)，i是下一个子串的起点；在i..n-1范围内枚举终点j，只要s[i..j]是回文就选取它并递归处理j+1之后的剩余部分，返回后pop撤销。基础条件是i == len(s)时把part的拷贝收入结果。

仓库中的 python/0131-palindrome-partitioning.py 正是这一形态的完整实现：

class Solution: def partition(self, s: str) -> List[List[str]]: res, part = [], [] def dfs(i): if i >= len(s): res.append(part.copy()) return for j in range(i, len(s)): if self.isPali(s, i, j): part.append(s[i : j + 1]) dfs(j + 1) part.pop() dfs(0) return res def isPali(self, s, l, r): while l < r: if s[l] != s[r]: return False l, r = l + 1, r - 1 return True

该解法与双索引写法在决策语义上等价：双索引写法的「切分决策 + 不切分延伸」展开后，恰好覆盖了按起点枚举中「以i为起点、终点j从i扫到n-1」的全部子串；区别仅在于状态组织方式。按起点枚举版更简洁，是面试中最推荐的表达。

同目录下的多语言实现结构一致，可对照阅读：

• cpp/0131-palindrome-partitioning.cpp：dfs(s, start, curr, result)，以start == s.size()为终止条件，isPalindrome双指针校验；
• go/0131-palindrome-partitioning.go：用闭包backtrack(idx)，结果追加时显式复制append([]string{}, curr...)，避免共享底层数组；
• rust/0131-palindrome-partitioning.rs：is_palindrome将&String转为as_bytes()后按字节比较；
• swift/0131-palindrome-partitioning.swift：先把s映射为[Character]数组，再用Array(characters[start...end])切片判回文。

以 C++ 为例，仓库实现通过curr.pop_back()完成回溯撤销，与 Python 的part.pop()一一对应：

class Solution { public: vector<vector<string>> partition(string s) { vector<string> curr; vector<vector<string>> result; dfs(s, 0, curr, result); return result; } private: void dfs(string s, int start, vector<string>& curr, vector<vector<string>>& result) { if (start == s.size()) { result.push_back(curr); return; } for (int i = start; i < s.size(); i++) { if (isPalindrome(s, start, i)) { string str = s.substr(start, i - start + 1); curr.push_back(str); dfs(s, i + 1, curr, result); curr.pop_back(); } } } bool isPalindrome(string s, int left, int right) { while (left < right) { if (s[left] != s[right]) return false; left++; right--; } return true; } };

5. DP 预计算回文表：把回文校验降为 O(1)

纯回溯的问题在于：同一子串s[i..j]可能被不同递归分支反复校验，最坏情况下每个子串被检查O(2^n)次，浪费大量时间（这也是 articles/palindrome-partitioning.md 末尾「Common Pitfalls」专门警示的点）。

优化方案是用动态规划一次性预计算所有回文子串，建立二维表dp[i][j]：

• dp[i][j] = true表示s[i..j]是回文；
• 按子串长度l从 1 到n递增填充：
  • 长度为 1 的单字符天然是回文；
  • 更长的子串满足：s[i] == s[j]且内部s[i+1..j-1]是回文（或长度 ≤ 2）。

预计算完成后，回溯中的isPali(s, i, j)调用全部替换为dp[i][j]的查表操作，每次判定降为O(1)。时间复杂度仍为O(n * 2^n)（答案数量主导），但常数大幅下降；额外空间变为O(n^2)用于存放 DP 表。仓库中 java/0131-palindrome-partitioning.java 与 cpp/0131-palindrome-partitioning.cpp 均为纯回溯版本，而 articles/palindrome-partitioning.md 的第 3 节给出了完整的「Backtracking (DP)」多语言模板，可直接作为该优化的参考实现。

6. 纯递归返回式：无全局状态的声明式写法

另一种优雅的实现是返回式递归（articles/palindrome-partitioning.md 第 4 节「Recursion」）：不维护全局res与part，而是让dfs(i)返回从i出发的所有回文分割方案。

• 基础条件：i == len(s)时返回[[]]（一个空分割）；
• 递归逻辑：对每个满足dp[i][j]的j，先递归取得dfs(j+1)的所有方案，再把s[i..j]前置拼接到每个方案头部；
• 组合公式即：所有从 i 出发的分割 = 选择回文 s[i..j] + 所有从 j+1 出发的分割。

这种写法的优点是完全无副作用、逻辑自明，缺点是每个节点都要新建列表，内存分配更多。仓库的 java/0131-palindrome-partitioning.java 采用了与之思想一致的递归结构：对每个满足回文条件的前缀s.substring(0, i+1)，递归求解后缀partition(s.substring(i+1))并把前缀插到每个结果的头部。

7. 常见陷阱自查清单

综合提示文档与 articles/palindrome-partitioning.md 的「Common Pitfalls」一节，提交前务必检查三点：

1. 结果必须存拷贝而非引用：part在回溯过程中会被反复修改，直接res.append(part)会让所有结果指向同一份最终被清空的列表。正确写法是part.copy()（Python）、new ArrayList<>(part)（Java）、append([]string{}, part...)（Go）等。
2. 基础条件用i >= len(s)（或==）而非i > len(s)：i越过末尾意味着起点已经消费完整个字符串；写成>会漏掉恰好在末尾完成切分的合法方案，或引发越界。
3. 避免无记忆化的重复回文校验：同一子串在不同分支被反复判定会拖慢长字符串场景，建议用第 5 节的 DP 表缓存。

8. 总结：解法谱系与复杂度一览

四种写法共享同一复杂度上界O(n * 2^n)，差异集中在常数因子与代码风格。练习时建议从按起点枚举的回溯入手（对应 python/0131-palindrome-partitioning.py），再对照 articles/palindrome-partitioning.md 掌握双索引、DP 预计算与返回式递归的变体，最后用第 7 节的自查清单规避全部经典陷阱——这套能力可以平移到「分割回文串 II」「单词拆分」等同族回溯问题。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode