1

我正在解决回文分区问题，该问题需要返回给定字符串的所有回文分区（http://oj.leetcode.com/problems/palindrome-partitioning/）。我找到了两个解决这个问题的方法。我很难理解为什么这两种方法的运行时间存在巨大差异：

（假设bool isPal()是一个给定的函数，它告诉给定的字符串在 O(length) 时间内是否是回文）

第一种解决方案：（使用回溯）：

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

第二种解决方案：

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

尽管两种解决方案的基本思想相同，但第一种解决方案的运行时间为108ms，而第二种解决方案的运行时间为472ms。这是因为理论上的效率低下（可能第二个解决方案多次解决了一个问题）还是因为实现效率低下（一些 C++ 概念）？请指出第二种解决方案效率低下的原因。

注意：两种解决方案都是正确的并给出相同的结果。

4

1 回答 1

1

我假设两种实现都返回相同的结果？除此之外，还有一些值得评论的行：

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

这会强制将 的所有内容sub_answer[j]移回给s1. 最好s1在添加其余部分之前添加到向量中。

answer.push_back(sub_answer[j]);

sub_answer[j]现在又被复制了。由于您不再需要sub_answer[j]，您可以使用std::move交换所有权而不是复制：

answer.push_back(std::move(sub_answer[j]));
于 2013-09-21T04:12:41.350 回答