Longest Common Subsequence

Dynamic Programming

avgO(m·n)worstO(m·n)spaceO(m·n)

Cell [i][j] will hold the LCS length of the first i letters of "AGGTAB" and the first j letters of "GXTXAYB"

1 / 55

Code

function lcs(a: string, b: string) {  const m = a.length, n = b.length;  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1));  for (let j = 0; j <= n; j++) dp[0][j] = 0;  for (let i = 1; i <= m; i++) dp[i][0] = 0;  for (let i = 1; i <= m; i++) {    for (let j = 1; j <= n; j++) {      if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);    }  }  let i = m, j = n, out = "";  while (i > 0 && j > 0) {    if (a[i - 1] === b[j - 1]) {      out = a[i - 1] + out;      i--; j--;    } else if (dp[i - 1][j] >= dp[i][j - 1]) i--;    else j--;  }  return out;}

procedure LCS(A, B)  m ← |A|; n ← |B|  dp ← (m + 1) × (n + 1) table  for j ← 0 to n do dp[0][j] ← 0    ▷ empty prefix of A  for i ← 1 to m do dp[i][0] ← 0    ▷ empty prefix of B  for i ← 1 to m do    for j ← 1 to n do      if A[i] = B[j] then dp[i][j] ← dp[i − 1][j − 1] + 1      else dp[i][j] ← max(dp[i − 1][j], dp[i][j − 1])    end for  end for  i ← m; j ← n; S ← ""    ▷ walk back from the corner  while i > 0 and j > 0 do    if A[i] = B[j] then      prepend A[i] to S      i ← i − 1; j ← j − 1    else if dp[i − 1][j] ≥ dp[i][j − 1] then i ← i − 1    else j ← j − 1  end while  return Send procedure

Variables

m=6n=7

Counters

cells filled: 0

How it works

Finds the longest sequence of letters that appears in both strings in the same order, not necessarily side by side. Cell [i][j] holds the answer for the first i letters of a and the first j letters of b: a matching pair extends the diagonal by one, otherwise the better of dropping a letter from either string wins. Walking back from the corner recovers the subsequence itself.

Complexity

Best: O(m·n)
Average: O(m·n)
Worst: O(m·n)
Space: O(m·n)

Longest Common Subsequence

How it works

Complexity

Search algorithms