Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
class Solution {
public:
std::vector<std::vector<std::string>> partition(std::string s) {
std::vector<std::vector<std::string>> result;
std::vector<std::string> ans;
dfs(s,ans,result);
#if 0
for (int i = 0; i < result.size(); i++)
{
for (int j = 0; j < result[i].size(); j++)
{
std::cout << result[i][j] << " ";
}
std::cout << std::endl;
}
#endif // 1
return result;
}
private:
void dfs(std::string s,std::vector<std::string> &ans,std::vector<std::vector<std::string>> &result)
{
if(s.size() < 1)
{
result.push_back(ans);
return ;
}
for (int i = 0; i < s.size(); i++)
{
int a = 0,b = i;
while(a < b)
{
if(s[a] == s[b]) a++,b--;
else break;
}
if(a >= b)
{
ans.push_back(s.substr(0,i+1));
dfs(s.substr(i+1),ans,result);
ans.pop_back();
}
}
}
};