DP on Strings

When you change a file and ask version control what is different, it does not compare line 1 with line 1 and give up after the first insert. It finds the largest set of lines that appear in both versions in the same order, even with other lines between them. It keeps those and reports everything else as added or removed.

Shrink the lines to letters and you get a puzzle you can do by hand. What is the longest sequence of letters that appears, in order, in both ROAD and BOARD? The letters do not have to sit next to each other, only keep their order. The answer is OAD, length 3. This is the longest common subsequence, or LCS.

#Prefixes are the subproblems

A word of length 4 has 16 subsequences and one of length 20 has over a million, so listing them is out. Instead, look at the last letter of each word.

• If they match, like the final D of ROAD and BOARD, use that letter. The rest of the answer is the LCS of what comes before: ROA and BOAR.
• If they differ, they cannot both be the last letter of a shared sequence. So at least one of them is not used: drop the last letter of one word or of the other, and keep the better result.

Either way the question becomes the same question about shorter prefixes: the first i letters of one word and the first j of the other. That gives a table with one word down the side and the other across the top.

#The five steps

1. State. L[i][j] is the length of the LCS of the first i letters of a and the first j letters of b.
2. Recurrence. If a[i − 1] == b[j − 1], then L[i][j] = L[i − 1][j − 1] + 1. Otherwise L[i][j] = max(L[i − 1][j], L[i][j − 1]).
3. Base cases. L[0][j] = 0 and L[i][0] = 0: an empty word shares nothing.
4. Order. Each cell reads up, left and diagonally up-left, as on a grid. Row by row, left to right.
5. Answer. L[len(a)][len(b)], the bottom-right cell.

Note the shift: row i is about the letter a[i − 1]. The extra row and column at index 0 stand for the empty prefix, and they are what make the base cases this simple.

L[i][0] = 0 and L[0][j] = 0for i from 1 to len(a):  for j from 1 to len(b):    if a[i-1] == b[j-1]:      L[i][j] = L[i-1][j-1] + 1    else:      L[i][j] = max(L[i-1][j], L[i][j-1])return L[len(a)][len(b)]

function lcsLength(a, b) {
  const L = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        L[i][j] = L[i - 1][j - 1] + 1; // use the matching letter
      } else {
        L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]); // drop one letter
      }
    }
  }
  return L[a.length][b.length];
}
 
lcsLength("ROAD", "BOARD"); // 3

def lcs_length(a, b):
    L = [[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]:
                L[i][j] = L[i - 1][j - 1] + 1  # use the matching letter
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])  # drop one letter
    return L[len(a)][len(b)]
 
lcs_length("ROAD", "BOARD")  # 3

#Same table, different question: edit distance

A spell checker sees the typo ROAD and wonders if you meant BOARD. It measures how close two words are by the fewest single-letter edits that turn one into the other, where an edit is inserting a letter, deleting a letter or replacing one letter with another. This is the edit distance.

The subproblems are prefixes again. Think about the last letters. If they match, they cost nothing: keep them and solve the shorter prefixes. If not, the last edit was one of three things, and each one points at a neighbouring cell.

1. State. E[i][j] is the fewest edits that turn the first i letters of a into the first j letters of b.
2. Recurrence. If the letters match, E[i][j] = E[i − 1][j − 1]. Otherwise E[i][j] = 1 + min(E[i − 1][j − 1], E[i − 1][j], E[i][j − 1]): replace, delete or insert.
3. Base cases. E[i][0] = i, since turning i letters into nothing takes i deletes. E[0][j] = j: building j letters from nothing takes j inserts.
4. Order and answer: the same as for LCS.

The corner says 2: replace R with B, then insert R before the D. Trace one cell to check yourself. Row O, column O is a match, so it copies the diagonal, row R and column B, which holds 1.

function editDistance(a, b) {
  const E = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
  for (let i = 0; i <= a.length; i++) E[i][0] = i; // delete everything
  for (let j = 0; j <= b.length; j++) E[0][j] = j; // insert everything
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        E[i][j] = E[i - 1][j - 1]; // free match
      } else {
        E[i][j] = 1 + Math.min(E[i - 1][j - 1], E[i - 1][j], E[i][j - 1]);
      }
    }
  }
  return E[a.length][b.length];
}
 
editDistance("ROAD", "BOARD"); // 2

def edit_distance(a, b):
    E = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        E[i][0] = i  # delete everything
    for j in range(len(b) + 1):
        E[0][j] = j  # insert everything
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                E[i][j] = E[i - 1][j - 1]  # free match
            else:
                E[i][j] = 1 + min(E[i - 1][j - 1], E[i - 1][j], E[i][j - 1])
    return E[len(a)][len(b)]
 
edit_distance("ROAD", "BOARD")  # 2

#Common mistakes

#Check yourself

#What to practise next

The last lesson of the module, Longest Increasing Subsequence, asks for a subsequence again, this time inside a single list of numbers. It starts as a one-row table and then gets much faster with binary search. To practise this lesson, try Shared Dance Moves for LCS and Spelling Test Fixes for edit distance.