R.A.N.K.A.'s blog

By R.A.N.K.A., history, 2 years ago, In English

Problem Link : https://www.interviewbit.com/problems/longest-common-subsequence/

Can anyone help me out.

why this code is giving time limit error(tle):

int fun(vector<vector<int> > &dp,int i,int j,string s1,string s2)
{
        if(i==s1.length()|| j==s2.length()) return 0;
        int &ans=dp[i][j];
        if(ans!=-1) return ans;
        ans=max(fun(dp,i,j+1,s1,s2),fun(dp,i+1,j,s1,s2));
        if(s1[i]==s2[j])
            ans=max(ans,1+fun(dp,i+1,j+1,s1,s2));
        return ans;
    }

 
int Solution::solve(string s1, string s2) {
    if(!s1.length() || !s2.length())    return 0;
    int n=s1.size(),m=s2.size();
    vector<vector<int> > dp(n,vector<int> (m,-1));
    return fun(dp,0,0,s1,s2);
}

and why this code get accepted:

×

int Solution::solve(string s1, string s2) {
    if(!s1.length() || !s2.length())    return 0;
    int n=s1.size(),m=s2.size(),i,j;
    vector<vector<int> > dp(n+1,vector<int> (m+1,0));
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(s1[i-1]==s2[j-1])
                dp[i][j]=1+dp[i-1][j-1];
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    return dp[n][m];
}

both solutions have time complexity O(m*n) memoization gives tle and tabulation passes the constraints why?? Thanks in advance.

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by R.A.N.K.A. (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Try passing the strings by reference in the recursive solution. Since you are passing them by value, each time a new temporary copy is created, which is a costly operation. This might be the reason for TLE