Is my solution backtracking and why was it slow?


  • 0
    Y

    The idea was simple: find the first palindrome and append it to the partition results from the rest of the string; then find the next palindrome and do the same, until end of string is reached. In the code below, I did the search backwards to avoid using vector.insert().

    If I expand the recursion, I see it doing the same as backtracking. But why did it run so much slower (taking >100ms)? I appreciate you sharing your thoughts on this.

    bool ispalindrome(string s) {
        int i, j;
        i = 0; j = s.size() - 1;
        while (i<j) {
            if (s[i]!=s[j]) return false;
            ++i; --j;
        }
        return true;
    }
    vector<vector<string>> partition(string s) {
        vector<vector<string> > ans;
        for (int i=s.size()-1; i>=0; --i) {
            if (ispalindrome(s.substr(i))) {
                if (i==0) {
                    vector<string> temp(1,s);
                    ans.push_back(temp);
                }
                else {
                    vector<vector<string>> rest = partition(s.substr(0,i));
                    for (int j=0; j<rest.size(); ++j) {
                        rest[j].push_back(s.substr(i));
                        ans.push_back(rest[j]);
                    }
                }
            }
        }
        return ans;
    }

Log in to reply
 

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