原题链接
一. 题目描述
给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是 回文串。返回 s
所有可能的分割方案。
示例 1:
输入:s = "aab" 输出:[["a","a","b"],["aa","b"]]
示例 2:
输入:s = "a" 输出:[["a"]]
提示:
1 <= s.length <= 16
s
仅由小写英文字母组成
二. 解题思路
首先得明确什么是回文串,回文串就是能够对称的字符串,还是老样子。
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)