题目描述
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
样例
输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]
算法1
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
string s;
int a[N];
vector<string> path;
//判断是否回文
bool isPalindrome(int star, int end){
for(int i = star, j = end; i < j; i++, j--){
if(s[i] != s[j]) return false;
}
return true;
}
void backtracking(string s, int starindex){
//终止条件
if(starindex >= s.size()){
for(int i = 0; i < path.size(); i++)
cout << path[i] <<' ';
cout <<endl;
return ;
}
//递归
for(int i = starindex; i < s.size(); i++){
//如果【starindex,i】区间内为回文,存入path
//否则跳过
if(isPalindrome(starindex, i)) {
string str = s.substr(starindex, i - starindex+1);
path.push_back(str);
}
else continue;
backtracking(s, i+1);
path.pop_back();
}
}
int main(){
cin >> s;
backtracking(s, 0);
return 0;
}