leetcode131分割回文串

递归树
在这里插入图片描述
下面这个代码是遍历处所有的子串

#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;
}