递归树
下面这个代码是遍历处所有的子串
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<string>> vvs;
vector<string> vs;
vector<vector<string>> partition(string s) {
dfs(0,s);
return vvs;
}
void dfs(int idx,string& s){
if(idx==s.size()){
vvs.push_back(vs);
return;
}
for(int i=idx;i<s.size();++i){
string str=s.substr(idx,i-idx+1);
// if(isOk(str)){
// vs.push_back(str);
// }else {
// continue;
// }
vs.push_back(str);
dfs(i+1, s);
vs.pop_back();
}
}
bool isOk(string& s){
for(int i=0,j=s.size()-1;i<j;++i,--j){
if(s[i]!=s[j]){
return 0;
}
}
return 1;
}
};
int main(){
vector<vector<string>> vvs=Solution().partition("abbc");
for(auto& vs:vvs){
for(auto& s:vs){
cout<<s<<" ";
}
cout<<endl;
}
cout<<"-----------------------------------"<<endl;
return 0;
}
结果如下
加入判断逻辑(isOk函数判断是否回文),如果当前遍历的子串是回文串,则添加到vector数组vs里面
如果不是回文,则中断当前的组合方案,pop当前末尾字母上去,一直往上回溯。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<string>> vvs;
vector<string> vs;
vector<vector<string>> partition(string s) {
dfs(0,s);
return vvs;
}
void dfs(int idx,string& s){
if(idx==s.size()){
vvs.push_back(vs);
return;
}
for(int i=idx;i<s.size();++i){
string str=s.substr(idx,i-idx+1);
if(isOk(str)){
vs.push_back(str);
}else {
continue;
}
dfs(i+1, s);
vs.pop_back();
}
}
bool isOk(string& s){
for(int i=0,j=s.size()-1;i<j;++i,--j){
if(s[i]!=s[j]){
return 0;
}
}
return 1;
}
};
int main(){
vector<vector<string>> vvs=Solution().partition("abbc");
for(auto& vs:vvs){
for(auto& s:vs){
cout<<s<<" ";
}
cout<<endl;
}
cout<<"-----------------------------------"<<endl;
string s="aaba";
cout<<s.substr(1,2)<<endl;
return 0;
}