Print LCS wrong WA

#1

Hey, can u pls tell me what is wrong in my code
here’s the link


it shows WA for 1st test case

#2

Hello @archit_18 ,
This happening due the following confusion at the time of backward traversal or at the time you are adding characters to ans:

Suppose, the elements of dp[3][3],
0 0 0
0 1 1
0 0 1
the element at a[2] != b[2], so you should move upward. But, in actual your code is moving diagonally at this case.

0 0 0
0 0 1
0 1 1
the element at a[2] != b[2], in which direction should you move, upward or leftward? It is something you should try by yourself.

These are the reasons causing wrong input.
So, while making dp[i][j], keep track of directions also:

  1. either make another array to store directions
  2. compare elements at a[i-1] and b[j-1] at the time of backward traversal.

Hope, this would help.
Give a like if you are satisfied.

#3

Suppose, the elements of dp[3][3],
0 0 0
0 1 1
0 0 1
for this input i guess my code will move upward, not diagonal
have a look
while(i>=0 && j>=0){
if(dp[i][j] == 1+dp[i-1][j-1]){
ans+=a[i-1];
i-=1;
j-=1;
}
else if(dp[i][j] == dp[i-1][j]){
–i;
}
else{
–j;
}
}
it will enter in else if cond, right?

#4

0 0 0
0 1 1
0 1 2
0 0 2

the element at a[3] != b[2], so you should move upward. But, in actual your code is moving diagonally at this case.

I typed that case wrongly.
Consider this example.

#5

while(i>=0 && j>=0){
if(dp[i][j] == 1+dp[i-1][j-1] && a[i-1] == b[j-1]){
ans+=a[i-1];
i-=1;
j-=1;
}
else if(dp[i][j] == dp[i-1][j]){
–i;
}
else{
–j;
}
}
is this work?

#6

it’s resolved now, thanks

#7

Please, mark this doubt as resolved if your queries are solved.
BTW, i wont mind a like.:joy:

#8

i dont know how to rate here or give u a like
is there any option to do that?

#9

LOL,
No, problem.

Btw you have an option to like the reply if you like it.
Also, you have an option to rate when you mark it as resolved.