Longest common subsequencce

#1

question–>


code–>

class Solution {
public:
    int lcs(string s1,string s2,int m,int n,int dp[][1001]){
        if(m==0 || n==0){
            return 0;
        }
        if(dp[m][n]!=-1){
            return dp[m][n];
        }
        if(s1[m-1]==s2[n-1]){
            return 1+lcs(s1,s2,m-1,n-1,dp);
        }
        else{
        int op1=lcs(s1,s2,m,n-1,dp);
        int op2=lcs(s1,s2,m-1,n,dp);
        return dp[m][n]=max(op1,op2);}
    }
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.length();
        int n=text2.length();
        int dp[1001][1001];
        memset(dp,-1,sizeof(dp));
        return lcs(text1,text2,m,n,dp);
    }
};

showing tle topdown approach

#2

but the bottom up approach is working fine

class Solution {
public:
    int lcs(string s1,string s2,int m,int n){
       int dp[1001][1001]={0};
        for(int i=0;i<=m;i++){
            for(int j=0;j<=n;j++){
                if(i==0 ||j==0){
                    dp[i][j]=0;
                }
                else 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[m][n];
    }
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.length();
        int n=text2.length();
        // int dp[1001][1001];/
        // for(int i=0;i<1001;i++){
        //     for(int j=0;j<1001;j++){
        //         dp[i][j]=-1;
        //     }
        // }
        return lcs(text1,text2,m,n);
    }
};
#3

Base case mai m<0 || n<0 krke dekhna

#4

nope it is not working

#5

they are expecting bottom up approach because in test case it showing like this

[43/43 all test cases pass but (TLE)]
#6

See you can save a lot of time, as i did by submitting your code. Pass all parameter by address. As once kartik also told you that pass by value takes a lot of time whereas pass by address doesn’t.
Moreover declare dp array as global. You are initializing it every time, thus it’s giving tle
Do this and you code will pass.

#7

array,2d array are passed by reference right

#8

Do it like this

int dp[1001][1001];
   int lcs(string &s1,string &s2,int m,int n){
        if(m==0 || n==0){
            return 0;
        }
        if(dp[m][n]!=-1){
            return dp[m][n];
        }
        if(s1[m-1]==s2[n-1]){
            return dp[m][n]=1+lcs(s1,s2,m-1,n-1);//updated in your code, you weren't giving it dp[m][n]
        }
        else{
        int op1=lcs(s1,s2,m,n-1);
        int op2=lcs(s1,s2,m-1,n);       
        return dp[m][n]=max(op1,op2);
        }
    }
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.length();
        int n=text2.length();
        //int dp[1001][1001];
        memset(dp,-1,sizeof(dp));
        return lcs(text1,text2,m,n);
    }
#9

But each time you are initializing it in longestCommonSubsequence that too with fixed size then why not declare it as global
43*(1001)*(1001) times
which you can do only one time only

#10

ohh got it string should passed by reference because everytime a new string is formed that’s what @tusharaggarwal272 told

#11

yes it is now passing all testcases when passed the string by reference ,(top down) thanks @mr.encoder

#12

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#13

See this, you will get an idea of how it works