# Description

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"]
]
``````

The original problem is here.

The original code is here.

# My Solution

I solve this problem in C++, as below:

``````/*
*Palindrome Partitioning
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
*/
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;

class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
int len = s.length();
if(len <= 0)
return result;
vector<string> path;
dfs(s, path, result, 0, 1);
return result;
}
void dfs(string &s, vector<string> &path, vector<vector<string>> &result, int prev, int start){
if(start == s.size()){
if(isPalindrome(s, prev, start-1)){
path.push_back(s.substr(prev, start-prev));
result.push_back(path);
path.pop_back();
}
return;
}
dfs(s, path, result, prev, start+1);
if(isPalindrome(s, prev, start-1)){
path.push_back(s.substr(prev, start-prev));
dfs(s, path, result, start, start+1);
path.pop_back();
}
return;
}
bool isPalindrome(string & s, int start, int end){
while(s[start] == s[end]){
start ++;
end --;
}
if(start < end)
return false;
else
return true;
}
};
``````

# Note

To solve the problem, depth-first search was used.