CODEWITHSUNDEEP
c++performancebacktracking
Koderok
Koderok

Reputation: 1933

Comparison of running times - similar code runs 4 times slower

I am solving the palindrome partition problem which requires to return all palindrome partitions of a given string (http://oj.leetcode.com/problems/palindrome-partitioning/). I found two solutions to this problem. I am having difficulty to understand why there is a huge difference in the running times of these two approaches:

(Assume bool isPal() is a given function which tells whether given string is palindrome or not in O(length) time)

1st Solution: (Uses backtracking):

void find(string s, int start, vector<string> &r, vector<vector<string> > &res){
    if (start >= s.size()){
        res.push_back(r);
    }else{
    for (int i=start;i<s.size();i++){            
        if (isPal(s.substr(start, i-start+1))){
            r.push_back(s.substr(start,i-start+1));
            find(s,i+1,r,res);        
            r.pop_back();
        }  
    }
    }  
}

vector<vector<string>> partition(string s) {
    vector<vector<string> > res;
    vector<string> r;
    find(s,0,r,res);
    return res;    
}

2nd Solution:

vector<vector<string> > partition(string s) {
    vector<vector<string> > answer;

    if(s.size() == 0)
        return answer;

    // if s is Palindrome, push to answer
    if(isPal(s))
        answer.push_back(vector<string>(1,s));

    if(s.size() == 1)
        return answer;

    for(int i=1; i<s.size(); ++i) {
        string s1 = s.substr(0, i);
        string s2 = s.substr(i, s.size()-i);

        if(isPal(s1)) {
            // get sub_answers of partition(s[i:])
            vector<vector<string> > sub_answer = partition(s2);

            // add s1 to the begin of sub_answers
            for(int j=0; j<sub_answer.size(); ++j) {
                sub_answer[j].insert(sub_answer[j].begin(), s1);
                answer.push_back(sub_answer[j]);
            }
        }
    }
    return answer;
}

Even though both the solutions have the same underlying idea, the 1st solution runs in 108ms, while the 2nd one takes 472ms time. Is this because of theoretical inefficiency (maybe 2nd solution solves a single problem multiple times) or because of inefficient implementation (some C++ concepts)? Please point out the reason for inefficiency of 2nd solution.

Note: Both solutions are correct and give the same result.

Upvotes: 1

Views: 144

Answers (1)

youdontneedtothankme
youdontneedtothankme

Reputation: 672

I assume both implementations returns the same result? Other than that, there are to lines worth commenting:

sub_answer[j].insert(sub_answer[j].begin(), s1);

This forces all the content of sub_answer[j] to be shifted back to give space to s1. Better add s1 to the vector before adding the rest.

answer.push_back(sub_answer[j]);

sub_answer[j] is now copied again. Since you don't need sub_answer[j] any more, you may use std::move to swap ownership in stead of copying:

answer.push_back(std::move(sub_answer[j]));

Upvotes: 1

Related Questions