12ms 14-lines C++


  • 29

    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();
                }
            }
        }
    };

  • 2
    Y

    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?


  • 0

    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.


  • 0
    Y

    Okay, I guess that's fine :D


  • 0
    L

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


  • 0
    S

    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();
                }
            }
        }
    };
    

  • 0

    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--;

  • 0
    G

    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.


Log in to reply
 

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