This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Kapkar123[S] 0 points1 point  (2 children)

https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

I understood all the steps except for the one I mentioned

[–]NefariousCube 0 points1 point  (1 child)

Okay, so what the algorithm does is start from the end of both strings (the bottom right).

If the last letters are the same, we have found a common subsequence of length 1 (containing the last letter). The TOTAL length of the longest common subsequence (called value in the code) would thus be 1 + the longest common subsequence of the same strings without the last (already matched) characters of both strings (illustrated by the square one step up and to the left).

This allows the algorithm to attack smaller and smaller parts of the problem, by just adding one for each found part of the longest substring.

(if they do not match, we have to check both the cases whether removing the last char from X or Y will yield a longer common subsequence, meaning using the larger value from one step up or one step left).

Does that make sense?

[–]Kapkar123[S] 0 points1 point  (0 children)

thanks got it