(回溯) LeetCode 131. 分割回文串
原题链接
一. 题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
二. 解题思路
首先得明确什么是回文串，回文串就是能够对称的字符串，还是老样子。
1. 明确递归参数：字符串s 和当前路径的起点 startindex 。
2. 确定递归的终止条件：当startindex 的大小超过字符串的长度的时候终止，证明已经切割到了字符串的最后，直接将path 路径添加到结果数组res 中即可，这里小伙伴可能要问了，你这还没有判断是不是回文串，对，因为我在后面的单层递归中做了限制，只有回文子串才能进path 数组。所以这里的path 数组中一定是回文子串。
3. 单层递归逻辑：相信做了这么多的题目了，一定知道怎么写吧，只需要加一条判断是不是回文子串的限制条件即可，如果是将其加入到path 数组中进行递归即可，如果不是直接continue；最后做好回溯即可。
话不多说！！！上代码！！
三. 代码
class Solution {
public:vector<vector<string>> res;vector<string> path;bool isPalindrome(string s, int l, int r){ // 判断是不是回文子串for(int i = l, j = r; i <= j; i++, j--){if(s[i] != s[j]) return false;}return true;}void back(string s, int startindex){if(startindex >= s.size()){res.push_back(path);return;}for(int i = startindex; i < s.size(); i++){if(isPalindrome(s, startindex, i)){string str = s.substr(startindex, i - startindex + 1);path.push_back(str);back(s, i + 1);path.pop_back(); // 回溯}}}vector<vector<string>> partition(string s) {back(s, 0);return res;}
};四. 总结
如果你将前面的题目做了练习的话相信这类题目已经非常简单了吧！！！继续加油！！！
时间复杂度：O(n * 2^n)
空间复杂度：O(n^2)