LCS with 3 Strings

#1


my code is missing only one test case , pls help to correct it .

#2

@Sejalrathi,
I have corrected your code: https://ide.codingblocks.com/s/189951
I have implemented a different approach.

The idea is to take a 3D dp to store the length of common subsequence in all 3 given sequences .

If any of the string is empty then there is no common subsequence at all then dp[i][j][k] = 0

If the characters of all sequences match (or X[i] == Y[j] ==Z[k]) then dp[i][j][k] = 1 + dp[i-1][j-1][k-1]

If the characters of both sequences do not match (or X[i] != Y[j] || X[i] != Z[k] || Y[j] !=Z[k]) then L[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])

#3

That’s ohk , I got this approach but what was wrong in my approach ? It was missing only one test case , so there might be a slight error only …
Pls help to correct that too .

#4

@Sejalrathi,
https://ide.codingblocks.com/s/190748 I have corrected your original code.

The problem was, you were taking strings in the order of a,b,c. And then taking reverse of LCS(a,b) with string c. But it might be possible that reverse of LCS(a,c) with string b returns a larger result. Since you were taking only 1 case. It was causing a wrong answer. I have added 2 more conditions along with it a Math.max function. Kindly have a look.

#5

Got it .
Thank u so much.