# Two c++ solutions

• the first one is inspired by Word Break II,56ms,no extra function

``````class Solution {
public:
vector<vector<string>> partition(string s) {
if(mp.count(s))return mp[s];
vector<vector<string>> res;
if(s.size()==0)res.push_back(vector<string>());
else{
for(int i=s.size()-1;i>=0;i--){
int lo=i,hi=s.size()-1;
while(lo<hi){
if(s[lo]!=s[hi])break;
lo++,hi--;
}
if(lo>=hi){
vector<vector<string>> pre=partition(s.substr(0,i));
for(auto&k:pre){
k.push_back(s.substr(i));
res.push_back(k);
}
}
}
}
mp[s]=res;
return res;
}
private:
unordered_map<string,vector<vector<string>>> mp;
};
``````

the second one is faster and the first thought that hit my mind,a general dfs solution.

``````class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> tmp;
partition(res,tmp,s);
return res;
}
void partition(vector<vector<string>>& res,vector<string>& tmp,string s){
if(!s.size())
if(tmp.size())res.push_back(tmp);
for(int i=0;i<s.size();i++){
int lo=0,hi=i;
while(lo<hi){
if(s[lo]!=s[hi])break;
lo++,hi--;
}
if(lo>=hi){
tmp.push_back(s.substr(0,i+1));
partition(res,tmp,s.substr(i+1));
tmp.pop_back();
}
}
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.