Print LCS getting 1 case wrong

#1

Getting 1 test case wrong in this code .

#2

string s1,s2;
cin>>s1>>s2;

ll n1 = s1.length();
ll n2 = s2.length();

ll dp[n1+2][n2+2]={0};
for(ll i=0;i<=n1;i++){
    for(ll j=0;j<=n2;j++){
        dp[i][j]=0;
    }
}

for(ll i=1;i<=n1;i++){
    for(ll j=1;j<=n2;j++){
        if(s1[j-1]==s2[i-1]){
            dp[i][j] = dp[i-1][j-1] + 1;
        }else{
            dp[i][j]  = max(dp[i-1][j] , dp[i][j-1]);
        }
    }
}

string s="";
ll i=n1,j=n2;
while(i>0 && j>0){
    if(s1[j-1]==s2[i-1]){
        s+=s1[j-1];
        i--;
        j--;
    }else{
        if(dp[i-1][j] > dp[i][j-1]){
            i--;
        }else{
            j--;
        }
    }
}

reverse(s.begin(),s.end());

cout<<s<<"\n";
#3

hi aryan,
your logic and thinking is correct.
In implementation,only at two points you are interchanging the two strings due to which DP table is not forming correctly.
You can refer to this edited code for more understanding.

1 Like
#4

okay , thankyou sir !!