day154—回溯—分割回文串（LeetCode-131）
题目描述
给你一个字符串s，请你将s分割成一些 子串，使每个子串都是回文串。返回s所有可能的分割方案。
示例 1：
输入：s = "aab"输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
解决方案：
这段代码的核心功能是将一个字符串分割成若干个子串，且每个子串都是回文串，输出所有可能的分割方案（比如输入 "aab"，输出[["a","a","b"],["aa","b"]]），采用「回溯 + 回文校验」的思路实现，是字符串回文分割问题的经典解法。
核心逻辑
成员变量作用：
t：临时数组，存储当前正在构造的回文分割方案（比如分割到某一步时，t 可能是 ["a","a"]）；ans：最终结果数组，存储所有合法的回文分割方案；tmp：未使用的临时变量（可删除，不影响功能）。
辅助函数
isPalindrome：- 功能：校验字符串
s中从left到right的子串是否为回文（正读和反读一致）； - 实现：双指针从两端向中间遍历，逐一对比字符，只要有一对不相等就返回 false，否则返回 true。
- 功能：校验字符串
递归函数
dfs逻辑：- 参数
curr：表示当前分割的起始位置（从字符串的第curr位开始尝试分割）；str：待分割的原始字符串； - 终止条件：当
curr == str.size()时，说明已经把字符串完整分割完毕，此时t就是一个合法的分割方案，将其加入ans后返回； - 核心流程（枚举分割点 + 回溯）：① 遍历从
curr到字符串末尾的所有位置j（j是当前分割的结束位置）；② 校验：如果str中[curr, j]区间的子串是回文，则将该子串加入临时数组t；③ 递归：以j+1为新的起始位置，继续分割剩余的字符串；④ 回溯：递归返回后，执行t.pop_back()删掉刚加入的子串，尝试下一个分割点。
- 参数
主函数
partition：- 从起始位置
0调用dfs，启动递归分割过程； - 最终返回存储所有合法分割方案的
ans。
- 从起始位置
关键特点
- 核心思想：通过「枚举分割点 + 回文校验」，确保每一步分割出的子串都是回文，再递归处理剩余部分，回溯保证能尝试所有可能的分割方式；
- 去重逻辑：分割点
j从curr开始遍历，保证分割顺序是 “从左到右不回头”，避免生成重复的分割方案（比如不会出现 ["b","aa"] 这种逆序分割，因为curr会逐步后移）。
总结
- 核心思路：递归枚举所有可能的分割点，仅保留 “分割出的子串是回文” 的分支，递归到底时收集完整的分割方案；
- 关键操作：
isPalindrome校验回文是前提，t.push_back()（记录合法分割）和t.pop_back()（回溯）是实现所有方案遍历的核心； - 功能效果：能输出字符串的所有 “全回文子串” 分割方案，无重复、无遗漏。
以输入 "aab" 为例，最终会生成两种合法方案：
- 分割为 ["a","a","b"]（每一步分割的子串 "a"、"a"、"b" 都是回文）；
- 分割为 ["aa","b"]（子串 "aa"、"b" 都是回文）。
函数源码：
class Solution { public: vector<string> t; vector<vector<string>> ans={}; string tmp; bool isPalindrome(const string& s, int left, int right) { while (left < right) { if (s[left++] != s[right--]) { return false; } } return true; } void dfs(int curr,string str){ int len = str.size(); if(curr==len){ ans.push_back(t); return ; } for(int j=curr;j<len;j++){ if(isPalindrome(str,curr,j)){ t.push_back(str.substr(curr, j - curr + 1)); // 分割！ dfs(j+1,str); t.pop_back(); } } } vector<vector<string>> partition(string s) { dfs(0,s); return ans; } };