Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ]
class Solution {
public:
vector<vector<string> > ans;
bool check(string s)
{
int i=0,j=s.size()-1;
while(i<j)
{
if(s[i]!=s[j])
return false;
++i,--j;
}
return true;
}
void partition(string s,vector<string> &res)
{
if(s.size()==0)
ans.push_back(res);
for(int k=0;k<s.size();++k)
{
if(check(s.substr(0,k+1)))
{
res.push_back(s.substr(0,k+1));
partition(s.substr(k+1),res);
res.pop_back();
}
}
}
vector<vector<string>> partition(string s)
{
vector<string> res;
partition(s,res);
return ans;
}
};
