函数参数传值与传引用对时间复杂度的影响及TLE问题咨询

在Coding Ninja的「分割回文串」题目中，使用void solve(int index,string &s,vector<vector<string>> &ans,vector<string> &temp)可以通过所有测试用例，但使用void solve(int index,string s,vector<vector<string>> &ans,vector<string> &temp)时，最后一个测试用例会出现TLE（超时）。

以下是两段对应代码：

使用引用传递string的代码 #

bool isPalindrome(string &s, int start, int end) {
    while(start <= end) {
        if(s[start++] != s[end--]) {
            return false;
        }
    }
    return true;
}

void helper(int idx, string &s, vector<string> &path, vector<vector<string>> &ans) {
    if(idx == s.size()) {
        ans.push_back(path);
        return;
    }

    for(int i=idx; i<s.size(); i++) {
        if(isPalindrome(s, idx, i)) {
            path.push_back(s.substr(idx, i - idx + 1));
            helper(i + 1, s, path, ans);
            path.pop_back();   
        }
    }
}

vector<vector<string>> partition(string s) {
    vector<string> path;
    vector<vector<string>> ans;
    helper(0, s, path, ans);
    return ans;
}

不使用引用传递string的代码 #

bool ispartition(string s,int start,int end)
{
    while(start<=end)
    {
        if(s[start++]!=s[end--])
        return false;

    }
    return true;
}
void solve(int index,string s,vector<vector<string>> &ans,vector<string> &temp)
{
    if(index==s.size())
    {
        ans.push_back(temp);
        return;
    }
    for(int i=index;i<s.size();i++)
    {
        if(ispartition(s,index,i))
        {
            temp.push_back(s.substr(index,i-index+1));
            solve(i+1,s,ans,temp);
            temp.pop_back();
        }
    }
}

vector<vector<string>> partition(string s) {
    // Write your code here.
    vector<vector<string>> ans;
    vector<string> temp;
    solve(0,s,ans,temp);
    return ans;
}

请问为何传递string时不使用引用（&）会导致时间复杂度上升进而出现TLE？

• 字符串拷贝的指数级开销：按值传递string时，每次调用solve或ispartition函数，都会创建原字符串的完整拷贝，这个操作的时间复杂度是O(n)（n为字符串长度）。而分割回文串的递归调用次数是指数级的（最坏情况比如全相同字符的字符串，递归树节点数达O(2^{n)），这会让总时间复杂度从原本的O(n*2}n)（每个分割的回文检查是O(n)，加上2^{n次递归调用）飙升至O(n²*2}n)，长字符串场景下直接触发超时。
• 回文检查的额外拷贝消耗：不使用引用的版本中，ispartition函数也按值接收string，每次检查回文时又多了一次字符串拷贝，进一步放大了时间消耗。而引用版本的isPalindrome直接操作原字符串，无拷贝开销。
• 内存占用的间接影响：大量字符串拷贝会占用更多内存，引发频繁的内存分配与回收，增加运行时额外开销，间接拖慢程序速度。

内容的提问来源于stack exchange，提问作者kingoftypos-