Find the error in the code

#1
#2

Your computed 2D dp array is correct. But there’s some problem in the logic when you are trying to find the LCS.
while((i!=0)&&(j!=0))
{
if((dp[i][j-1]==dp[i-1][j])&&(dp[i][j]!=dp[i-1][j]))
{
i = i-1;
j = j-1;
s.push(s1[i]);
}
else if((dp[i][j-1]==dp[i-1][j])&&(dp[i][j]==dp[i-1][j]))
j = j-1;
else
{
if(dp[i][j]==dp[i-1][j])
i=i-1;
else
j=j-1;
}
}

Check this code for finding the LCS and tell me if you are able to understand it.

1 Like
#3

Thank you I got the logic behind ur code.
But can u explain what is the fault in my this piece version of the code.
I used the logic which was given in the hint video.
I feel I am making some error in the priority order of checking the conditions.
while(i>=0 && j>=0)
{
if(dp[i][j]==(dp[i-1][j-1]+1))
{
s.push(s1[i-1]);
i=i-1;
j=j-1;
}
else if(dp[i][j-1]>dp[i-1][j])
{
j=j-1;
}
else
{
i=i-1;
}
}

#4

I suggest you to take two strings, construct the 2D dp array on paper and dry run both the versions. You will get to know about your mistake.
You can take any two strings which give different answers when run on both the codes.

#5

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.