Longest Common Subsequence
Step-by-Step Animation
Animation Speed
Elaboration:
?
Longest Common Subsequence: Given two strings, It finds the longest subsequence of them.
Recursive Approach: we define a function lcs(i, j) where i and j is a index pointer to string 1 and string 2 respectively.
lcs(i, j) =
{
0 i < 0 or j < 0
lcs(i - 1, j - 1) str1[i] = str2[j]
Max(lcs(i - 1, j), lcs(i, j - 1)) otherwise
Memoization: We use a table to store key-value pairs where the key is n, and the value is fib(n). If key is in the table, we can return instantly.