# 8ms c++ dp+dfs solution

• ``````    vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<string>> result;
if(n == 0) {
return result;
}
// First dp to find all palindromes
// isPalindromes[i][j]: is substring s(i,j) palindrome
bool **isPalindrome = new bool*[n];
for(int i = 0; i < n; i++) {
isPalindrome[i] = new bool[n];
}
for(int i = 1; i < n; i++) {
isPalindrome[i][i-1] = true;
}
for(int i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
for(int length = 2; length <= n; length++) {
for(int i = 0; i <= (n - length); i++) {
isPalindrome[i][i+length-1] = isPalindrome[i+1][i+length-2] && (s[i] == s[i+length-1]);
}
}
vector<string> tmp;
// Then dfs to find all partitions
findPartitions(s, 0, tmp, result, isPalindrome);

for(int i = 0; i < n; i++) {
delete [] isPalindrome[i];
}
delete [] isPalindrome;
return result;
}

void findPartitions(string s, int k, vector<string>& tmp, vector<vector<string>>& partitions, bool **isPalindrome) {
int n = s.size();
if(k == n) {
partitions.push_back(tmp);
return;
}
for(int i = k; i < n; i++) {
if(isPalindrome[k][i]) {
tmp.push_back(s.substr(k, i-k+1));
findPartitions(s, i+1, tmp, partitions, isPalindrome);
tmp.pop_back();
}
}
}``````

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