We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Hi Alexhans,
check the wikipedia page for the Longest Common Subsequent problem: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
You have to find the length of the longest subsequence common to the both of the strings, and it's different from the problem of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions.
Subsequence definition: "In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements".
Consider X = XMJYAUZ and Y = MZJAWXU
The longest common subsequence between X and Y is MJAU
As you can see, in the subsequences there can be missing chars (compared to the original strings), but the important thing is that any char in the common subsequence is present in both the input strings (in the same order).
The simple recursive solution does not have complexity of O(N^2) time. It is way much bigger, because of the branching. Take a look at Cormen's chapter on the problem.
Magic Spells
You are viewing a single comment's thread. Return to all comments →
Hi Alexhans,
check the wikipedia page for the Longest Common Subsequent problem: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
You have to find the length of the longest subsequence common to the both of the strings, and it's different from the problem of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions.
Subsequence definition: "In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements".
Consider X = XMJYAUZ and Y = MZJAWXU
The longest common subsequence between X and Y is MJAU
As you can see, in the subsequences there can be missing chars (compared to the original strings), but the important thing is that any char in the common subsequence is present in both the input strings (in the same order).
Thank you very much, Danilo. That really helped.
This was a great example of a solution that required memoization because the simple recursive solution has a complexity of O(N^2).
Hello Alexhans,
I'm really pleased that my answer was helpful :D
Thank you sooo much for the endorsement!
Danilo, You really help! Thanks, really good way to teach. It is better than code, more useful.
Thank you for your kind words :D
Hello Danilo, can i say that intersection of the characters present in the two strings, can be defined as the longest subsequence??
The simple recursive solution does not have complexity of O(N^2) time. It is way much bigger, because of the branching. Take a look at Cormen's chapter on the problem.
The real horror show is that LCS is not guaranteed to be single valued. There can be multiple equally valid LCS.
What an awful, awful addition to an inheritance "lesson."
okay it is clear now but why in type casting include problem like this and why they don't include anything about it
Gracias!!! Realmente no entendía el problema.