DFS + dp solution

• Idea is to use DP to avoid checking palindromes redundantly. Consider substring [i, j] - if we know that substring [i+1,j-1] is a palindrome and S[i] == S[j] then we know for sure [i,j] is also a palindrome. For the rest we just use conventional backtracking DFS approach to trace the paths.

``````class Solution {
public:
vector<vector<string>> partition(string s) {
vector<string> path;
vector<vector<string>> res;
populate_dp(s);
dfs(s, 0, s.size(), path, res);
return res;
}

void dfs(string &s, int i, int j, vector<string> &p, vector<vector<string>> &r) {
if (i == j) {
r.push_back(p);
return;
}

for (int k=i; k < j; ++k) {
if (dp[i][k]) {
p.push_back(s.substr(i, k-i+1));
dfs(s, k+1, j, p, r);
p.pop_back();
}
}

}

void populate_dp(string &s) {
dp.resize(s.size());
for (auto &v: dp) v.resize(s.size());

for (int i=0;i < s.size(); ++i) dp[i][i] = 1;
for (int i=1; i < s.size(); ++i) dp[i-1][i] = (s[i-1] == s[i]);

for (int sz=3; sz <= s.size(); ++sz) {
for (int i=0; i <= s.size()-sz; ++i) {
int j=i+sz-1;
dp[i][j] = (s[i] == s[j]) && (dp[i+1][j-1]==1);
}
}
}

vector<vector<uint8_t>> dp;
};
``````

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