Given two strings str1 and str2, find length of the longest common sub-sequence between them
All Answers
total answers (1)
Severity: 8192
Message: str_replace(): Passing null to parameter #3 ($subject) of type array|string is deprecated
Filename: libraries/Filtered_db.php
Line Number: 23
total answers (1)
The problem can be solved in a brute-force way. By generating all sub-sequences and checking them whether equal or not. Finally taking the longest common subsequence. But undoubtedly this is not at all computable since generating all sub-sequence is itself exponential and then permutations for checking any two sub-sequences.
The recursive way to solve is
Let,
Now,
Think of the following example,
Say first string is: x1 x2 ... xl1
And the second string is: y1 y2 ... yl2
Say,![](https://www.includehelp.com/icp/Images/longest-common-subsequence-a.jpg)
Then obviously we need to find LCS for the remaining part of string
and then add 1 for this character match
Else
Maximum of two case
Now, we need to recur down to 0. So,
Where base cases are,
If you generate this recursion tree, it will generate many overlapping sub-problems and thus, we need to reduce the re-computing. That’s why we need to convert it into dynamic programming where we will store the output of the sub-problems and we will use it to compute bigger sub-problems.
Converting to Dynamic programing
C++ Implementation:
Output