12ms 14-lines C++

• The problem has a nice structure that backtracking naturally fits in. The structure is, given a starting position `idx`, we search from `idx` till the end of the string `s.length() - 1`. Once we reach a position `i` such that the sub-string from `idx` to `i` (`s.substr(idx, i - idx + 1)`) is a palindrome, we add it to a temporary `tmp`. Then we recursively call the same function to process the remaining sub-string. Once we reach the end of the string, we add `tmp` into the result `res` of all the possible partitioning.

Then, backtracking happens! Remember that at position `i`, we find `s.substr(idx, i - idx + 1)` to be a palindrome and we immediately add it to `tmp`. It is obvious that there may be some position `j` such that `j > i` and `s.substr(idx, j - idx + 1)` is also a palindrome. So we need to recover to the state before adding `s.substr(idx, i - idx + 1)` to `tmp` and continue to find the next palindrome position after `i`. And we simply need to pop `s.substr(idx, i - idx + 1)` out of `tmp` to make things work.

Putting these together, we can write down the following code, which should be self-explanatory.

``````class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> tmp;
getPartition(s, 0, tmp, res);
return res;
}
private:
void getPartition(string& s, int idx, vector<string>& tmp, vector<vector<string>>& res) {
if (idx == s.length()) {
res.push_back(tmp);
return;
}
for (int i = idx, n = s.length(); i < n; i++) {
int l = idx, r = i;
while (l < r && s[l] == s[r]) l++, r--;
if (l >= r) {
tmp.push_back(s.substr(idx, i - idx + 1));
getPartition(s, i + 1, tmp, res);
tmp.pop_back();
}
}
}
};``````

• Hi, is there repeating calculation in this algorithm though?
Such as, "cbcaba":

we will first found "c", "b", "c", then at this point, we are going to do recursion for "aba" to find all possible solutions for it ;
then later, we also find "cbc" is palindrome, so we are going to do calculation for "aba" again, but we have already done this before

is there any way to avoid this repeated calculation?

• Hi, yingying.chen.7370. I think what you see is right. However, since we need to generate all possible partitions, I guess those repeated calculations have to be done unless we can come up with a way to record them. But now I cannot come up with any simple way to record those information. So I still keep the code as it is.

• Okay, I guess that's fine :D

• you can use dp to avoid the duplicate calculation. use an array flag[i][j] to remember whether substring i->j is palindrome.

• Hi, Jianchao, I have a question, How can this be faster than DP solution?
As we know, there are some repeating sub problem when determining whether a substring in s is palindrome.
I wrote the DP solution, which needs 16ms to finish...

``````class Solution {
public:
vector<vector<string>> partition(string s) {
//first step is to find all the palindromes in the string
//then use dfs method to walk though the whole word using palindrome records

//dp[startindex][len] indicates whether s[start]~[start+len] is palindome
vector<vector<bool> > dp(s.size(), vector<bool>(s.size()+1, false));
for(int i=0;i<s.size();++i){
dp[i][0]=dp[i][1]=true;
}
for(int j=2;j<=s.size();++j){
for(int i=0;i+j<=s.size();++i){
dp[i][j]=dp[i+1][j-2]&&(s[i]==s[i+j-1]);
}
}
vector<vector<string>> finalRes;
vector<string> curRes;
dfs(s, 0, curRes, finalRes, dp);
return finalRes;
}
void dfs(string &s, int index, vector<string> &curRes, vector<vector<string>> &finalRes, vector<vector<bool> > &dp){
if(index==s.size()){
finalRes.push_back(curRes);
return;
}
for(int i=1;i+index<=s.size();++i){
if(dp[index][i]) {
curRes.push_back(s.substr(index, i));
dfs(s, index+i, curRes, finalRes, dp);
curRes.pop_back();
}
}
}
};
``````

• Hi, sydy72. By briefly reading your solutions, I do not see real improvements over the asymptotic time complexity of your algorithm. In fact, you also have a backtracking phase, which is the major time-consuming part of the solution. But you need to build the `dp` array and handling 2d array is also expensive (overhead). In my solution, I have the following additional line to check for palindromes, but I guess such a simple `while` loop is very fast.

``while (l < r && s[l] == s[r]) l++, r--;``

• Hi, I copied Jianchao.li's code and it returned 12ms; then I added flag[i][j] to his code (with int 2->not discovered, 1->yes pali, 0->no pali), it returned the same 12ms.

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