PRINT LCS problem

#1

MY code is giving error in one of the test cases. I’ve used stack for storing LCS. Please help me.
Code link: https://ide.codingblocks.com/s/160241

#2

Hey @raj.bmp.333
Just a few small errors in your code

  1. You need to write
    (dp[i-1][j]==dp[i][j-1])&&(dp[i-1][j-1]+1==dp[i][j])
    instead of
    (dp[i-1][j]==dp[i][j-1])&&(dp[i-1][j-1]+1==dp[i][i])
    (i guess just your typo of dp[i][i], write dp[i][j] instead)

  2. You need to write
    dp[i-1][j]>dp[i][j-1]
    instead of
    dp[i-1][j]>=dp[i][j-1]

#3

I didn’t get 2nd point. Why can’t we go up in dp matrix when dp[i-1][j] == dp[i][j-1] ?

#4

Hello @raj.bmp.333

When dp[i-1][j] == dp[i][j-1] you can go both left or up in the dp matrix, it won’t matter.
However the choice (up or left) may create difference in the output string. Output strings may be different when you choose left or when you choose up, but the length of both these strings will be equal and equal to the length of LCS.

1 Like