 # Pass by Value vs Pass by Reference in Recursion

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

TLE Code:

class Solution {
public:

``````int dp;

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;

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

};

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

1 Like