Comment on page

# 131.Palindrome Partitioning

131.Palindrome Partitioning

[
["aa","b"],
["a","a","b"]
]

class Solution {
public:
vector<vector<string>> partition(string s) {
int n=s.length(),cnt=0;
vector<vector<string>> res;
vector<string> ret;
if (n == 1)
{
ret.push_back(s);
res.push_back(ret);
return res;
}
vector<vector<string>> tmp;
for(int i=1;i<n;i++)
{
string fir=s.substr(0,i);
if(ispalind(fir))
{
tmp=merge(fir,partition(s.substr(i,n-i)));
res.insert(res.end(),tmp.begin(),tmp.end());
}
}
if(ispalind(s))
{
ret.push_back(s);
res.push_back(ret);
}
return res;
}
vector<vector<string>> merge(string a, vector<vector<string>>b)
{
vector<vector<string>> res;
for(int i=0;i<b.size();i++)
{
vector<string>tmp;
tmp.push_back(a);
tmp.insert(tmp.end(),b[i].begin(),b[i].end());
res.push_back(tmp);
}
return res;
}
bool ispalind(string s)
{
int n=s.length();
for(int i=0;i<n/2;i++)
if(s[i]!=s[n-i-1]) return false;
return true;
}
};

class Solution {
vector<vector<string>> res;
void DFS(string& s, int begin, vector<string>& t){
if(begin>=s.length())
res.push_back(t);
else{
t.push_back("");
for(int end=begin;end<s.length();end++)
if(isParl(s, begin, end)){
t[t.size()-1] = s.substr(begin, end-begin+1);
DFS(s, end+1, t);
}
t.pop_back();
}
}
bool isParl(string& s, int begin, int end){
// 可以用DP存储加速
while(begin<end){
if(s[begin]!=s[end])
return false;
begin++;
end--;
}
return true;
}
public:
vector<vector<string>> partition(string s) {
vector<string> t;
DFS(s, 0, t);
return res;
}
};