Longest Common Subsequence

Dynamic Programming: lesson 6 of 10

Match the two ends, or drop a character from one side.

Lesson 6 of 10 · 6 min

Longest Common Subsequence

Step 1 of 16

εeight

εnight

One row per prefix of night, one column per prefix of eight. Each cell is the answer for those two prefixes.

The Idea

Compare two sequences from the end inward. If the last characters match, the answer is the answer for both shorter prefixes plus one. If they differ, drop the last character of one string or the other and keep whichever gives more. A grid indexed by prefix lengths stores every one of those sub-answers exactly once.

Real-World Example

A contract review tool diffing two drafts. It finds the longest run of clauses that appear, in order, in both versions, then flags everything outside that alignment as inserted or deleted. The run does not have to be unbroken, so an added paragraph in the middle costs nothing.

The Code

def lcs(a, b):
    grid = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                grid[i][j] = grid[i - 1][j - 1] + 1        # matched: take the diagonal
            else:
                grid[i][j] = max(grid[i - 1][j], grid[i][j - 1])
    return grid[len(a)][len(b)]

print(lcs("ABCBDAB", "BDCABA"))   # 4
print(lcs("night", "eight"))      # 4

Your turn

Fill in the blank.

def lcs(a, b):
  g = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
  for i in range(1, len(a) + 1):
      for j in range(1, len(b) + 1):
          if a[i - 1] == b[j - 1]:
              g[i][j] = ___ + 1
          else:
              g[i][j] = max(g[i - 1][j], g[i][j - 1])
  return g[len(a)][len(b)]

print(lcs("common", "moon"))   # should print 3

Mini quiz

1 / 3

Longest Common Subsequence