Longest common subsequence (recursion)

Medium TimeO(2^(m+n)) naive; O(m·n) memoised SpaceO(m + n) stack

A subsequence keeps a string's order but may skip characters, so "ace" is a subsequence of "abcde". Given two strings, return the length of the longest subsequence they share. Characters may be skipped but never reordered, they need not be adjacent in either string, and two strings sharing nothing answer 0.

Examples

Example 1

Input
a = 'abcde'b = 'ace'i = 0j = 0
Output
3
a, c and e appear in that order in both, with b and d skipped.

Example 2

Input
a = 'abc'b = 'xyz'i = 0j = 0
Output
0
Not one character is common to both, so the longest shared subsequence is empty.

The Code

function lcs(a, b, i, j) {
  if (i === a.length || j === b.length) return 0;
  if (a[i] === b[j]) return 1 + lcs(a, b, i + 1, j + 1);
  return Math.max(lcs(a, b, i + 1, j), lcs(a, b, i, j + 1));
}
lcs('abcde', 'ace', 0, 0);
Done
Step through lcs('abcde', 'ace', 0, 0) call by call

More like this

All dynamic programming examples (20) →