Longest Common Subsequence

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

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