131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
题解思路
定义两个全局变量：
vector<vector<string> > result;
- 保存结果总和
vector<string> tmp;
- 用来存储每一种结果
c++要用到的函数：
basic_string substr( size_type index, size_type num = npos); // index 是从哪个位置开始截取 // num 是截取多少个字符
利用回溯算法来穷举
给出回溯模板:
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (//选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { //处理节点; backtracking(路径，选择列表); // 递归 // 回溯，撤销处理结果 } }
回溯也是递归，所以也可以按照递归三步走
- 确定参数和返回值
- 回溯算法不需要返回值
- 本题涉及截取子串，所以要增加一个参数，用来表示开始截取的位置
void backtracking(string s, int start);
- 确定终止条件
- 当截取的开始位置大于等于了字符串长度，则将其加入到
结果二维数组
if(start >= s.size()){ result.push_back(tmp); return ; }
- 确定本层逻辑
- 本层逻辑其实就是确定
for循环里面的内容 - 假设输入样例是
"aab"，backtracking的初始参数为(s, 0) - 直接给出核心代码 我解释他们的意思
for(int i = start; i < s.size(); i++){ if(isHuiwen(start, i, s)){ tmp.push_back(s.substr(start, (i - start) + 1)); }else { continue; } backtracking(s, i + 1); tmp.pop_back(); }
- 当
i等于0的时候的那一层for循环 -> 一定会出一个结果，就是每个字符单独的时候也就是["a", "a", "b"]，当i++后，i变成1，substr里面的函数就会是(0, 1)就会截取"aa"字符，之后再添加一个"b"，形成第二种结果，在最后一次外层for循环时，i为2，此时截取的字符为"aab"，则直接结束。 。。。我已经看不下去我解释的了 以后再来该改改吧
- 反正要想得通的一点是，对于最外层的
for循环（没有进入递归的时候），start一直是0，进入后因为传参是加了1所以start才会变
完整代码
class Solution { public: bool isHuiwen(int left, int right, const string &a){ for(int i = left, j = right; i < j; i++, j--){ if(a[i] != a[j]) return false; } return true; } vector<vector<string>> result; vector<string> tmp; void backtracking(string s, int start){ if(start >= s.size()){ result.push_back(tmp); return ; } for(int i = start; i < s.size(); i++){ if(isHuiwen(start, i, s)){ tmp.push_back(s.substr(start, (i - start) + 1)); }else { continue; } backtracking(s, i + 1); tmp.pop_back(); } } vector<vector<string>> partition(string s) { backtracking(s, 0); return result; } };
