Pass by Value vs Pass by Reference in Recursion

general
1

Why passing string by reference in recursion makes code get accepted while passing by value gets TLE?

Problem Link: - LeetCode
TLE Code:

class Solution {
public:

int dp[1001][1001];

int min_del(string s1,string s2,int i,int j)
{
    if(dp[i][j]!=-1)
    {
        return dp[i][j];
    }
    if(i>=s1.length() && j>=s2.length())
    {
        return 0;
    }
     
    if(i>=s1.length()) 
    {
       return dp[i][j]=(int)(s2[j])+min_del(s1,s2,i,j+1);;
    }
    
    if(j>=s2.length())
    {
       return dp[i][j]=(int)(s1[i])+min_del(s1,s2,i+1,j);;
    }
   
    if(s1[i]==s2[j])
    {
        return (dp[i][j]=min_del(s1,s2,i+1,j+1));
    }
    int a=(int)(s1[i])+min_del(s1,s2,i+1,j);
    int b=(int)(s2[j])+min_del(s1,s2,i,j+1);
    
    
    return (dp[i][j]=min(a,b));
    
}
int minimumDeleteSum(string s1, string s2) 
{
    
  memset(dp,-1,sizeof(dp));
    
  
    return (min_del(s1,s2,0,0));
}

};

Accepted Code:

class Solution {
public:

int dp[1001][1001];

int min_del(string &s1,string &s2,int i,int j)
{
    if(dp[i][j]!=-1)
    {
        return dp[i][j];
    }
    if(i>=s1.length() && j>=s2.length())
    {
        return 0;
    }
     
    if(i>=s1.length()) 
    {
       return dp[i][j]=(int)(s2[j])+min_del(s1,s2,i,j+1);;
    }
    
    if(j>=s2.length())
    {
       return dp[i][j]=(int)(s1[i])+min_del(s1,s2,i+1,j);;
    }
   
    if(s1[i]==s2[j])
    {
        return (dp[i][j]=min_del(s1,s2,i+1,j+1));
    }
    int a=(int)(s1[i])+min_del(s1,s2,i+1,j);
    int b=(int)(s2[j])+min_del(s1,s2,i,j+1);
    
    
    return (dp[i][j]=min(a,b));
    
}
int minimumDeleteSum(string s1, string s2) 
{
    
  memset(dp,-1,sizeof(dp));
    
  
    return (min_del(s1,s2,0,0));
}

};

2

If you pass it by value, for every call, the string is copied and adds an additional O(n) complexity

1 Like