Print LCS : 2D DP

#1

Sir it’s showing wrong answer for one of the test cases. Don’t know where my code went wrong. Kindly help.
Code : ide.codingblocks.com/s/188079

#2

The 2D array which you have computed is correct.
There is some problem with the part where you are finding the common string.
Dry run your code for the input -
abbve
gbdea
You will find the mistake.

#3

My code is giving desired output the the test case you have given

#4

Check this piece of code for finding the common string and tell me if you get the logic -

string common="";
int i=n, j=m;
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;
common = s1[i] + common;
}
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;
}
}

#5

But what is the issue with my code ?

#6

If you take a look at my code, I am not reducing the value of j at every step, like you have done in your code. So it is giving a wrong answer in one of the test cases.

#7

@aman2382000 Please mark your doubt as resolved if you are satisfied.

#8

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.

#9

Coding blocks ide is under maintanance. please send your code on another ide.