1. 题目描述1.1 原始题目给定一个字符串s请你将s分割成一些子串使每个子串都是回文串。返回s所有可能的分割方案。回文串定义正读和反读都一样的字符串如 “aba”、“a”、“aa”约束条件1 s.length 16 s 仅由小写英文字母组成1.2 示例详解示例 1输入s aab 输出[[a,a,b],[aa,b]]分析方案1a a b ↓ ↓ ↓ a a b 全部是回文 ✓ 方案2aa b ↓ ↓ aa b 全部是回文 ✓示例 2输入s a 输出[[a]]分析只有一个字符本身就是回文只有一种分割方式1.3 约束分析s.length 16 -- 字符串很短可以用暴力搜索重要虽然数据规模小但分割方案数量是指数级的每个位置都可以选择分割或不分割2. 解题思路总览2.1 核心思想步骤操作目的1从左到右枚举每个切割位置确定当前子串边界2判断当前子串是否为回文剪枝非回文不继续搜索3是回文则加入路径继续递归深度优先搜索4递归返回后撤销选择回溯恢复现场5枚举完所有位置记录结果到达终止条件2.2 方法对比方法时间复杂度空间复杂度说明暴力枚举O(2^(n-1) * n)O(n)枚举所有分割方式预处理回溯O(2^(n-1) * n)O(n) O(n^2)预计算回文减少判断DP优化O(n^2)O(n^2)用DP存储回文结果本文方法预处理回文回溯2.3 递归搜索树以 s “aab” 为例[根节点: 空] | v 枚举位置0-2 | ------------------------------ | | | v v v 位置0切分 位置0-1切分 位置0-2切分 a|ab aa|b aab不可行 | | v v a|a|b aa|b | | v v [[a,a,b]] [[aa,b]]3. 完整代码classSolution{public:// 判断子串 s[l..r] 是否为回文串boolis_palinedrome(conststrings,intl,intr){while(lr){if(s[l]!s[r--])returnfalse;}returntrue;}vectorvectorstringpartition(string s){intns.size();vectorvectorstringans;// 最终结果vectorstringpath;// 当前的分割方案// 使用 lambda 定义递归 DFS 函数autodfs[](thisautodfs,inti,intstart){// 终止条件已经处理到字符串末尾if(in){ans.emplace_back(path);return;}// 尝试不切割直接向右扩展if(in-1){dfs(i1,start);}// 检查 s[start..i] 是否为回文串if(is_palinedrome(s,start,i)){// 是回文加入路径path.emplace_back(s.substr(start,i-start1));// 递归处理下一个子串的起始位置dfs(i1,i1);// 回溯撤销选择path.pop_back();}};dfs(0,0);returnans;}};4. 算法流程图4.1 主函数流程[开始 partition] | v n s.size() ans [], path [] | v dfs(0, 0) | v [DFS搜索] | v 返回 ans | v [结束]4.2 DFS函数详细流程dfs(i, start) | v i n ? / \ 是 否 | | v v 加入ans 继续 | | v v return i n-1 ? / \ 是 否 | | v v dfs(i1, start) 跳过不切割 | | v v is_palinedrome 检查回文 (s, start, i) | | v / \ s[start..i] 是回文? 是 否 / \ | | 是 否 v v | | path.push 跳过 v v | 返回 切割 跳过 v | dfs(i1, i1) v | path.push v dfs(i1, i1) path.pop | | v v path.pop return (回溯)4.3 递归路径图解以 s “aab” 为例展示完整的递归路径dfs(0, 0) -- 位置0不切割a | v dfs(1, 0) -- 位置1不切割aa | v dfs(2, 0) -- 位置2不切割aab | s[0..2]aab 不是回文跳过 v dfs(3, 0) -- in到达终止条件 | v path[] → ans.push_back([[]]) [路径1] 返回到 dfs(2, 0)检查 s[0..2]aab 不是回文 返回到 dfs(1, 0)检查 s[0..1]aa 是回文 | v path.push(aa) → path[aa] dfs(2, 1) -- 检查 s[1..2]ab 不是回文 | v dfs(3, 1) -- in到达终止条件 | v path[aa] → ans.push_back([[aa]]) [路径2] 返回到 dfs(1, 0)检查 s[1..1]a 是回文 | v path.push(a) → path[a] dfs(2, 1) -- 位置2检查 s[1..2]ab 不是回文 | v dfs(3, 1) -- in到达终止条件 | v path[a] → ans.push_back([[a]]) [路径3] 返回到 dfs(2, 1)检查 s[1..2]ab 不是回文 返回到 dfs(2, 0)检查 s[0..2]aab 不是回文 返回到 dfs(1, 0)检查 s[1..1]a 是回文第二个a | v path.push(a) → path[aa] dfs(2, 1) -- 检查 s[1..2]ab 不是回文 | v dfs(3, 1) -- in到达终止条件 | v path[aa] → ans.push_back([[aa]]) [路径2重复] 返回到 dfs(2, 1)检查 s[1..2]ab 不是回文 返回到 dfs(2, 0)检查 s[0..2]aab 不是回文 返回到 dfs(1, 0)检查 s[1..1]a 是回文 返回到 dfs(0, 0)检查 s[0..0]a 是回文 | v path.push(a) → path[a] dfs(1, 1) -- 位置1检查 s[1..2]ab 不是回文 | v dfs(2, 1) -- 位置2检查 s[1..1]a 是回文 | v path.push(a) → path[a,a] dfs(2, 2) -- 检查 s[2..2]b 是回文 | v path.push(b) → path[a,a,b] dfs(3, 2) -- in到达终止条件 | v path[a,a,b] → ans.push_back([[a,a,b]]) [路径4] 返回完成最终 ans [[a,a,b], [aa,b]]5. 逐行深度解析5.1 回文判断函数boolis_palinedrome(conststrings,intl,intr){while(lr){if(s[l]!s[r--])returnfalse;}returntrue;}语法含义const string s常量引用避免拷贝int l, int r子串的左右边界索引l r双指针当左指针小于右指针时继续s[l] ! s[r--]比较后自增返回不相等则falsereturn true循环正常结束说明是回文双指针原理aba: l0, r2 → aa → l1, r1 → lr不成立 → return true abb: l0, r2 → ab → return false5.2 主函数变量定义intns.size();vectorvectorstringans;// 所有合法分割方案vectorstringpath;// 当前正在构建的方案变量类型用途ansvectorvector二维结果第一维是不同方案第二维是每个方案中的子串pathvector一维路径记录当前分割方案nint字符串长度5.3 递归lambda定义autodfs[](thisautodfs,inti,intstart){参数含义i当前处理到的位置当前子串的结束位置start当前子串的起始位置捕获外部变量 n, ans, pathi 和 start 的关系当前子串是 s[start..i] 下一个子串起始位置是 i15.4 递归终止条件if(in){ans.emplace_back(path);return;}含义已经处理完所有字符将当前方案加入结果触发时机s aab, n3 dfs(3, 2) 时 in触发终止 此时 path 是完整的分割方案5.5 不切割的选择if(in-1){dfs(i1,start);}含义当前位置还不是末尾继续向右扩展字符不进行切割为什么需要这个选择分割可以在任意位置进行需要尝试继续扩展和进行切割两种选择5.6 切割并检查回文if(is_palinedrome(s,start,i)){path.emplace_back(s.substr(start,i-start1));dfs(i1,i1);path.pop_back();}判断是否切割is_palinedrome(s, start, i) 返回 true → s[start..i] 是回文可以切割 → 将子串加入 path → 递归处理下一个子串从 i1 开始步骤操作1判断 s[start…i] 是否为回文2是回文则 s.substr(start, i-start1) 提取子串3path.emplace_back() 加入当前方案4dfs(i1, i1) 递归处理下一个子串5path.pop_back() 回溯撤销5.7 回溯的本质path.emplace_back(...);// 做选择dfs(...);path.pop_back();// 撤销选择为什么需要回溯假设当前 path [a] 加入新子串 a 后 path [a, a] 递归处理完后需要恢复 path [a] 这样才能尝试其他选择撤销时机递归调用返回后立即撤销6. 复杂度分析6.1 时间复杂度O(2^(n-1) * n)推导长度为 n 的字符串最多有 n-1 个切割位置每个位置都可以选择切或不切最多 2^(n-1) 种分割方式每种方式需要 O(n) 时间判断回文最坏情况实际情况有回文剪枝实际搜索空间远小于 2^(n-1)6.2 空间复杂度O(n) -- 递归栈深度 O(n^2) -- path 存储包括子串拷贝组成递归栈深度最多 n 层path 最多存储 n 个子串每个子串平均长度 n/27. 递归过程详解7.1 s “aab” 的完整递归过程字符串位置索引位置: 0 1 2 字符: a a b start递归调用序列Level 0: dfs(0, 0) ├─ i0 n-1: dfs(1, 0) │ ├─ i1 n-1: dfs(2, 0) │ │ ├─ i2 n-1: dfs(3, 0) → ans.push_back([[]]) │ │ └─ s[0..2]aab 不是回文跳过 │ └─ s[0..1]aa 是回文 │ ├─ path.push(aa) │ ├─ dfs(2, 1) │ │ ├─ i2 n-1: dfs(3, 1) → ans.push_back([[aa]]) │ │ └─ s[1..2]ab 不是回文跳过 │ └─ path.pop() │ └─ s[0..0]a 是回文 │ ├─ path.push(a) │ ├─ dfs(1, 1) │ │ ├─ s[1..2]ab 不是回文跳过 │ │ └─ s[1..1]a 是回文 │ │ ├─ path.push(a) │ │ ├─ dfs(2, 2) │ │ │ ├─ s[2..2]b 是回文 │ │ │ │ ├─ path.push(b) │ │ │ │ ├─ dfs(3, 2) → ans.push_back([[a,a,b]]) │ │ │ │ └─ path.pop() │ │ │ └─ return │ │ └─ path.pop() │ └─ return └─ s[0..0]a 是回文 ├─ path.push(a) ├─ dfs(1, 1) │ └─ (同上的子路径已在上面处理) └─ path.pop()7.2 状态变化过程递归调用path状态操作ans变化dfs(0,0)[]开始[]dfs(1,0)[]继续扩展[]dfs(2,0)[]继续扩展[]dfs(3,0)[]终止[[]]返回dfs(2,0)[]s[0…2]不是回文[[]]dfs(2,1)[“aa”]继续扩展[[]]dfs(3,1)[“aa”]终止[[],[“aa”]]dfs(2,1)[“a”]继续扩展[[],[“aa”]]dfs(3,2)[“a”,“a”,“b”]终止[[],[“aa”],[“a”,“a”,“b”]]8. 易错点分析8.1 回文判断边界错误写法boolis_palinedrome(conststrings,intl,intr){while(lr){// 错误应该 l rif(s[l]!s[r--])returnfalse;}returntrue;}后果当 lr 时会多比较一次8.2 递归终止条件位置错误写法if(is_palinedrome(s,start,i)){// 先判断回文// ...}if(in){// 终止条件在后面ans.emplace_back(path);return;}后果可能漏掉空路径或提前终止8.3 忘记回溯错误写法if(is_palinedrome(s,start,i)){path.emplace_back(...);dfs(i1,i1);// 忘记 path.pop_back()}后果path 累积导致结果错误8.4 边界条件 i n-1错误写法if(in){// 错误会多递归一层dfs(i1,start);}后果i n-1 时还会递归 dfs(n, start)然后 in 触发终止但 start 可能不正确8.5 substr 参数错误错误写法path.emplace_back(s.substr(start,i-start));// 缺少 1后果子串长度少19. 边界条件测试9.1 单字符s a 输出[[a]] 分析只有一个字符本身就是回文9.2 全相同字符s aaa 输出[[a,a,a], [a,aa], [aa,a], [aaa]] 分析所有分割方式都是回文9.3 全部回文s aba 输出[[a,b,a], [aba]]9.4 无重叠回文s abc 输出[[a,b,c]] 分析只有每个字符单独是回文组合不成回文9.5 最长字符串s aabbccdd... (16个字符) 输出所有可能的分割方案2^15 32768种10. 面试追问 FAQ问题高分回答如何优化回文判断预处理用 DP 或中心扩展法预先计算所有 s[l…r] 是否为回文避免重复判断为什么用回溯而不是 DP回溯能枚举所有方案DP 通常只计数或求最优如何确保不重复从左到右搜索保证了顺序不会重复枚举可以并行搜索吗不可以回溯依赖状态累积必须顺序执行时间复杂度的 2^(n-1) 怎么来的n-1 个切割位置每个位置有切或不切两种选择如果 s 很长怎么办n16暴力搜索足够更长则需剪枝或采样和 131 类似的问题有哪些复原IP地址、括号生成、组合总和11. 相关题目对比题号题目难度核心区别131分割回文串Medium找所有回文分割方案93复原IP地址Medium按点分四段验证每段合法性22括号生成Medium验证左右括号匹配131分割回文串 IIHard求最小分割次数12. 总结要点详情算法回溯选择-递归-撤销核心函数is_palinedrome() 判断回文搜索方式从左到右枚举切割位置剪枝条件只切割回文子串时间复杂度O(2^(n-1) * n)空间复杂度O(n)
【力扣100题】74.分割回文串
发布时间：2026/5/31 10:27:15
1. 题目描述1.1 原始题目给定一个字符串s请你将s分割成一些子串使每个子串都是回文串。返回s所有可能的分割方案。回文串定义正读和反读都一样的字符串如 “aba”、“a”、“aa”约束条件1 s.length 16 s 仅由小写英文字母组成1.2 示例详解示例 1输入s aab 输出[[a,a,b],[aa,b]]分析方案1a a b ↓ ↓ ↓ a a b 全部是回文 ✓ 方案2aa b ↓ ↓ aa b 全部是回文 ✓示例 2输入s a 输出[[a]]分析只有一个字符本身就是回文只有一种分割方式1.3 约束分析s.length 16 -- 字符串很短可以用暴力搜索重要虽然数据规模小但分割方案数量是指数级的每个位置都可以选择分割或不分割2. 解题思路总览2.1 核心思想步骤操作目的1从左到右枚举每个切割位置确定当前子串边界2判断当前子串是否为回文剪枝非回文不继续搜索3是回文则加入路径继续递归深度优先搜索4递归返回后撤销选择回溯恢复现场5枚举完所有位置记录结果到达终止条件2.2 方法对比方法时间复杂度空间复杂度说明暴力枚举O(2^(n-1) * n)O(n)枚举所有分割方式预处理回溯O(2^(n-1) * n)O(n) O(n^2)预计算回文减少判断DP优化O(n^2)O(n^2)用DP存储回文结果本文方法预处理回文回溯2.3 递归搜索树以 s “aab” 为例[根节点: 空] | v 枚举位置0-2 | ------------------------------ | | | v v v 位置0切分 位置0-1切分 位置0-2切分 a|ab aa|b aab不可行 | | v v a|a|b aa|b | | v v [[a,a,b]] [[aa,b]]3. 完整代码classSolution{public:// 判断子串 s[l..r] 是否为回文串boolis_palinedrome(conststrings,intl,intr){while(lr){if(s[l]!s[r--])returnfalse;}returntrue;}vectorvectorstringpartition(string s){intns.size();vectorvectorstringans;// 最终结果vectorstringpath;// 当前的分割方案// 使用 lambda 定义递归 DFS 函数autodfs[](thisautodfs,inti,intstart){// 终止条件已经处理到字符串末尾if(in){ans.emplace_back(path);return;}// 尝试不切割直接向右扩展if(in-1){dfs(i1,start);}// 检查 s[start..i] 是否为回文串if(is_palinedrome(s,start,i)){// 是回文加入路径path.emplace_back(s.substr(start,i-start1));// 递归处理下一个子串的起始位置dfs(i1,i1);// 回溯撤销选择path.pop_back();}};dfs(0,0);returnans;}};4. 算法流程图4.1 主函数流程[开始 partition] | v n s.size() ans [], path [] | v dfs(0, 0) | v [DFS搜索] | v 返回 ans | v [结束]4.2 DFS函数详细流程dfs(i, start) | v i n ? / \ 是 否 | | v v 加入ans 继续 | | v v return i n-1 ? / \ 是 否 | | v v dfs(i1, start) 跳过不切割 | | v v is_palinedrome 检查回文 (s, start, i) | | v / \ s[start..i] 是回文? 是 否 / \ | | 是 否 v v | | path.push 跳过 v v | 返回 切割 跳过 v | dfs(i1, i1) v | path.push v dfs(i1, i1) path.pop | | v v path.pop return (回溯)4.3 递归路径图解以 s “aab” 为例展示完整的递归路径dfs(0, 0) -- 位置0不切割a | v dfs(1, 0) -- 位置1不切割aa | v dfs(2, 0) -- 位置2不切割aab | s[0..2]aab 不是回文跳过 v dfs(3, 0) -- in到达终止条件 | v path[] → ans.push_back([[]]) [路径1] 返回到 dfs(2, 0)检查 s[0..2]aab 不是回文 返回到 dfs(1, 0)检查 s[0..1]aa 是回文 | v path.push(aa) → path[aa] dfs(2, 1) -- 检查 s[1..2]ab 不是回文 | v dfs(3, 1) -- in到达终止条件 | v path[aa] → ans.push_back([[aa]]) [路径2] 返回到 dfs(1, 0)检查 s[1..1]a 是回文 | v path.push(a) → path[a] dfs(2, 1) -- 位置2检查 s[1..2]ab 不是回文 | v dfs(3, 1) -- in到达终止条件 | v path[a] → ans.push_back([[a]]) [路径3] 返回到 dfs(2, 1)检查 s[1..2]ab 不是回文 返回到 dfs(2, 0)检查 s[0..2]aab 不是回文 返回到 dfs(1, 0)检查 s[1..1]a 是回文第二个a | v path.push(a) → path[aa] dfs(2, 1) -- 检查 s[1..2]ab 不是回文 | v dfs(3, 1) -- in到达终止条件 | v path[aa] → ans.push_back([[aa]]) [路径2重复] 返回到 dfs(2, 1)检查 s[1..2]ab 不是回文 返回到 dfs(2, 0)检查 s[0..2]aab 不是回文 返回到 dfs(1, 0)检查 s[1..1]a 是回文 返回到 dfs(0, 0)检查 s[0..0]a 是回文 | v path.push(a) → path[a] dfs(1, 1) -- 位置1检查 s[1..2]ab 不是回文 | v dfs(2, 1) -- 位置2检查 s[1..1]a 是回文 | v path.push(a) → path[a,a] dfs(2, 2) -- 检查 s[2..2]b 是回文 | v path.push(b) → path[a,a,b] dfs(3, 2) -- in到达终止条件 | v path[a,a,b] → ans.push_back([[a,a,b]]) [路径4] 返回完成最终 ans [[a,a,b], [aa,b]]5. 逐行深度解析5.1 回文判断函数boolis_palinedrome(conststrings,intl,intr){while(lr){if(s[l]!s[r--])returnfalse;}returntrue;}语法含义const string s常量引用避免拷贝int l, int r子串的左右边界索引l r双指针当左指针小于右指针时继续s[l] ! s[r--]比较后自增返回不相等则falsereturn true循环正常结束说明是回文双指针原理aba: l0, r2 → aa → l1, r1 → lr不成立 → return true abb: l0, r2 → ab → return false5.2 主函数变量定义intns.size();vectorvectorstringans;// 所有合法分割方案vectorstringpath;// 当前正在构建的方案变量类型用途ansvectorvector二维结果第一维是不同方案第二维是每个方案中的子串pathvector一维路径记录当前分割方案nint字符串长度5.3 递归lambda定义autodfs[](thisautodfs,inti,intstart){参数含义i当前处理到的位置当前子串的结束位置start当前子串的起始位置捕获外部变量 n, ans, pathi 和 start 的关系当前子串是 s[start..i] 下一个子串起始位置是 i15.4 递归终止条件if(in){ans.emplace_back(path);return;}含义已经处理完所有字符将当前方案加入结果触发时机s aab, n3 dfs(3, 2) 时 in触发终止 此时 path 是完整的分割方案5.5 不切割的选择if(in-1){dfs(i1,start);}含义当前位置还不是末尾继续向右扩展字符不进行切割为什么需要这个选择分割可以在任意位置进行需要尝试继续扩展和进行切割两种选择5.6 切割并检查回文if(is_palinedrome(s,start,i)){path.emplace_back(s.substr(start,i-start1));dfs(i1,i1);path.pop_back();}判断是否切割is_palinedrome(s, start, i) 返回 true → s[start..i] 是回文可以切割 → 将子串加入 path → 递归处理下一个子串从 i1 开始步骤操作1判断 s[start…i] 是否为回文2是回文则 s.substr(start, i-start1) 提取子串3path.emplace_back() 加入当前方案4dfs(i1, i1) 递归处理下一个子串5path.pop_back() 回溯撤销5.7 回溯的本质path.emplace_back(...);// 做选择dfs(...);path.pop_back();// 撤销选择为什么需要回溯假设当前 path [a] 加入新子串 a 后 path [a, a] 递归处理完后需要恢复 path [a] 这样才能尝试其他选择撤销时机递归调用返回后立即撤销6. 复杂度分析6.1 时间复杂度O(2^(n-1) * n)推导长度为 n 的字符串最多有 n-1 个切割位置每个位置都可以选择切或不切最多 2^(n-1) 种分割方式每种方式需要 O(n) 时间判断回文最坏情况实际情况有回文剪枝实际搜索空间远小于 2^(n-1)6.2 空间复杂度O(n) -- 递归栈深度 O(n^2) -- path 存储包括子串拷贝组成递归栈深度最多 n 层path 最多存储 n 个子串每个子串平均长度 n/27. 递归过程详解7.1 s “aab” 的完整递归过程字符串位置索引位置: 0 1 2 字符: a a b start递归调用序列Level 0: dfs(0, 0) ├─ i0 n-1: dfs(1, 0) │ ├─ i1 n-1: dfs(2, 0) │ │ ├─ i2 n-1: dfs(3, 0) → ans.push_back([[]]) │ │ └─ s[0..2]aab 不是回文跳过 │ └─ s[0..1]aa 是回文 │ ├─ path.push(aa) │ ├─ dfs(2, 1) │ │ ├─ i2 n-1: dfs(3, 1) → ans.push_back([[aa]]) │ │ └─ s[1..2]ab 不是回文跳过 │ └─ path.pop() │ └─ s[0..0]a 是回文 │ ├─ path.push(a) │ ├─ dfs(1, 1) │ │ ├─ s[1..2]ab 不是回文跳过 │ │ └─ s[1..1]a 是回文 │ │ ├─ path.push(a) │ │ ├─ dfs(2, 2) │ │ │ ├─ s[2..2]b 是回文 │ │ │ │ ├─ path.push(b) │ │ │ │ ├─ dfs(3, 2) → ans.push_back([[a,a,b]]) │ │ │ │ └─ path.pop() │ │ │ └─ return │ │ └─ path.pop() │ └─ return └─ s[0..0]a 是回文 ├─ path.push(a) ├─ dfs(1, 1) │ └─ (同上的子路径已在上面处理) └─ path.pop()7.2 状态变化过程递归调用path状态操作ans变化dfs(0,0)[]开始[]dfs(1,0)[]继续扩展[]dfs(2,0)[]继续扩展[]dfs(3,0)[]终止[[]]返回dfs(2,0)[]s[0…2]不是回文[[]]dfs(2,1)[“aa”]继续扩展[[]]dfs(3,1)[“aa”]终止[[],[“aa”]]dfs(2,1)[“a”]继续扩展[[],[“aa”]]dfs(3,2)[“a”,“a”,“b”]终止[[],[“aa”],[“a”,“a”,“b”]]8. 易错点分析8.1 回文判断边界错误写法boolis_palinedrome(conststrings,intl,intr){while(lr){// 错误应该 l rif(s[l]!s[r--])returnfalse;}returntrue;}后果当 lr 时会多比较一次8.2 递归终止条件位置错误写法if(is_palinedrome(s,start,i)){// 先判断回文// ...}if(in){// 终止条件在后面ans.emplace_back(path);return;}后果可能漏掉空路径或提前终止8.3 忘记回溯错误写法if(is_palinedrome(s,start,i)){path.emplace_back(...);dfs(i1,i1);// 忘记 path.pop_back()}后果path 累积导致结果错误8.4 边界条件 i n-1错误写法if(in){// 错误会多递归一层dfs(i1,start);}后果i n-1 时还会递归 dfs(n, start)然后 in 触发终止但 start 可能不正确8.5 substr 参数错误错误写法path.emplace_back(s.substr(start,i-start));// 缺少 1后果子串长度少19. 边界条件测试9.1 单字符s a 输出[[a]] 分析只有一个字符本身就是回文9.2 全相同字符s aaa 输出[[a,a,a], [a,aa], [aa,a], [aaa]] 分析所有分割方式都是回文9.3 全部回文s aba 输出[[a,b,a], [aba]]9.4 无重叠回文s abc 输出[[a,b,c]] 分析只有每个字符单独是回文组合不成回文9.5 最长字符串s aabbccdd... (16个字符) 输出所有可能的分割方案2^15 32768种10. 面试追问 FAQ问题高分回答如何优化回文判断预处理用 DP 或中心扩展法预先计算所有 s[l…r] 是否为回文避免重复判断为什么用回溯而不是 DP回溯能枚举所有方案DP 通常只计数或求最优如何确保不重复从左到右搜索保证了顺序不会重复枚举可以并行搜索吗不可以回溯依赖状态累积必须顺序执行时间复杂度的 2^(n-1) 怎么来的n-1 个切割位置每个位置有切或不切两种选择如果 s 很长怎么办n16暴力搜索足够更长则需剪枝或采样和 131 类似的问题有哪些复原IP地址、括号生成、组合总和11. 相关题目对比题号题目难度核心区别131分割回文串Medium找所有回文分割方案93复原IP地址Medium按点分四段验证每段合法性22括号生成Medium验证左右括号匹配131分割回文串 IIHard求最小分割次数12. 总结要点详情算法回溯选择-递归-撤销核心函数is_palinedrome() 判断回文搜索方式从左到右枚举切割位置剪枝条件只切割回文子串时间复杂度O(2^(n-1) * n)空间复杂度O(n)
