# Sharing my C++ solution

• ``````class Solution {
private:
void dfs(string s, int k, vector<vector<bool>> DP, vector<string>& temp, vector<vector<string>>& result)
{
int n = s.length();
if(k==n)
{
result.push_back(temp);
return;
}

int i;
for(i=k; i<n; i++)
{
if(DP[k][i])
{
temp.push_back(s.substr(k, i-k+1));
dfs(s, i+1, DP, temp, result);
temp.pop_back();
}
}
}

bool isPalindrome(string s, int i, int j)
{
int left = i;
int right = j;
int n = s.length();
char str[n+1];
strcpy(str, s.c_str());
while(left<right)
{
if(str[left] != str[right])
return false;
left++;
right--;
}
return true;
}

public:
vector<vector<string>> partition(string s) {
int n = s.size();
char str[n+1];
strcpy(str, s.c_str());

vector<vector<bool>> DP; // DP[i,j]: whether substring[i,......,j] is palindrome
int i;
DP.resize(n);
for(i=0; i<n; i++)
DP[i].resize(n, false);

int j;
for(i=0; i<n; i++)
for(j=i; j<n; j++)
DP[i][j] = isPalindrome(s, i, j);

int len;
int start, end;
for(len=3; len<n; len++)
{
for(i=0; i<n-len; i++)
{
start = i;
end = i+len-1;
DP[start][end] = DP[start+1][end-1] && (str[start] == str[end]);
}
}

// Depth-first search
vector<vector<string>> result;
vector<string> temp;
dfs(s, 0, DP, temp, result);

return result;
}
};``````

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