Effect on time complexity of defining function argument in different ways

63 Views Asked by At

in a problem using void solve(int index,string &s,vector<vector> &ans,vector &temp) passes all test cases where as void solve(int index,string s,vector<vector> &ans,vector &temp) gives tle for the last test case in a problem on coding ninja can anyone help me why passing as a value and not the reference have an effect on time complexity

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


}
 

in first solution all test cases are passed whereas in second it's giving tle for only case can you explain why

tle when used without & and passed test case when used used with it.

0

There are 0 best solutions below