Edit Distance

The problem

You are given two words, a and b. One edit inserts one letter anywhere, deletes one letter, or replaces one letter with a different one. Return the smallest number of edits that turns a into b. If the two words are already equal, the answer is 0. Either word may be empty: an empty a becomes b by inserting each letter of b, and a becomes an empty b by deleting each of its letters.

What to write

function solve(a: string, b: string): number

Input
a = "horse"
b = "ros"

Output
3

Input
a = "intention"
b = "execution"

Output
5

Constraints

0–200 lowercase characters per string.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Each word has at most 200 letters. That rules out trying every sequence of edits, but it leaves room to do a little work for every pair of one position in a and one position in b: about 40,000 pairs. Either word may be empty, and then the answer is the length of the other word.

2. Hint 2: Ask a smaller question

   Turn ab into ac by hand, then ab into a, then ab into abc. Each takes one edit. In each case, what did you do with the last letter, and which shorter pair of words was left to deal with after that?

3. Hint 3: Name the pattern

   Whatever you do with the last letters, what is left is the same problem on a prefix of a and a prefix of b, a prefix being the first few letters of a word. The same pairs of prefixes come back again and again. Answer each pair once and keep the answers in a table: that is two-dimensional dynamic programming. Read the lesson on two-dimensional dynamic programming.

4. Hint 4: State the invariant

   The cell for a prefix of a and a prefix of b holds the fewest edits that turn the first into the second. Equal last letters: it equals the cell with both prefixes one letter shorter. Otherwise it is 1 plus the smallest of three cells: a prefix shorter (delete), b prefix shorter (insert), both shorter (replace).

5. Hint 5: Sketch the pseudocode

   Table with rows 0 to the length of a and columns likewise for b. Cell (i, 0) = i and cell (0, j) = j. Then row by row: if letter i of a equals letter j of b, copy the up-left cell. Otherwise 1 + the smallest of the cells above, left and up-left. Return the bottom right cell.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Build prefix edit distances. Equal last characters need no edit; otherwise choose the cheapest insertion, deletion, or replacement plus one.

The slow way

Compare the last letters. If they differ, try all three edits, solve what is left the same way, and keep the cheapest. It is correct, but the same leftovers are solved over and over. Turning intention into execution this way takes 1,709 calls, and two words of 10 letters with no letter in common take 12,146,179. The table for those two has 121 cells.

The insight

Look at the last letters of the two words. If they are equal, leave them alone and solve the rest. If not, an edit has to deal with them: delete the last letter of a, insert the last letter of b, or replace one with the other. Each choice costs 1 and leaves the same problem on shorter prefixes, a prefix being the first few letters of a word.

Step by step

1. Table: one row per prefix of word a, one column per prefix of word b. A cell holds the fewest edits that turn its row's prefix of a into its column's prefix of b. The empty prefix counts too, so each side has one more line than its word has letters.
2. First column: delete every letter of the prefix of word a. In the first column the prefix of b is empty, so nothing may remain. Deleting is the only useful edit, one per letter, so the cell in each row is the length of that row's prefix.
3. First row: insert every letter of the prefix of word b. In the first row the prefix of a is empty, so every letter has to be inserted. That costs one edit per letter, so the cell in each column is the length of that column's prefix.
4. For every other cell, compare the last letters of its two prefixes. What happens to the last letters decides which smaller cell the answer comes from. Going row by row, left to right, the cells above, to the left, and up and to the left are filled before they are needed.
5. Same letter: no edit is needed, so copy the cell up and to the left. Equal last letters already match, so they can be left alone. What remains is to turn the two prefixes without those letters into each other, and the cell up and to the left holds that count.
6. Different: one edit plus the smallest of three neighboring cells. Delete the last letter of the a prefix: the cell above. Insert the last letter of the b prefix: the cell to the left. Replace one with the other: the cell up and to the left. Each costs 1.
7. The bottom right cell turns all of word a into all of word b. The last row stands for all of a and the last column for all of b. Every cell this one was built from was already final, so its number is the answer.

The same numbered steps are the comments in each solution.

function solve(a, b) {
  // 1. Table: one row per prefix of word a, one column per prefix of word b
  const dp = Array.from({ length: a.length + 1 }, () =>
    Array(b.length + 1).fill(0),
  );
  // 2. First column: delete every letter of the prefix of word a
  for (let i = 0; i <= a.length; i++) dp[i][0] = i;
  // 3. First row: insert every letter of the prefix of word b
  for (let j = 0; j <= b.length; j++) dp[0][j] = j;
  // 4. For every other cell, compare the last letters of its two prefixes
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        // 5. Same letter: no edit is needed, so copy the cell up and to the left
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        // 6. Different: one edit plus the smallest of three neighboring cells
        dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
      }
    }
  }
  // 7. The bottom right cell turns all of word a into all of word b
  return dp[a.length][b.length];
}

function solve(a: string, b: string): number {
  // 1. Table: one row per prefix of word a, one column per prefix of word b
  const dp = Array.from({ length: a.length + 1 }, () =>
    Array(b.length + 1).fill(0),
  );
  // 2. First column: delete every letter of the prefix of word a
  for (let i = 0; i <= a.length; i++) dp[i][0] = i;
  // 3. First row: insert every letter of the prefix of word b
  for (let j = 0; j <= b.length; j++) dp[0][j] = j;
  // 4. For every other cell, compare the last letters of its two prefixes
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        // 5. Same letter: no edit is needed, so copy the cell up and to the left
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        // 6. Different: one edit plus the smallest of three neighboring cells
        dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
      }
    }
  }
  // 7. The bottom right cell turns all of word a into all of word b
  return dp[a.length][b.length];
}

def solve(a, b):
    # 1. Table: one row per prefix of word a, one column per prefix of word b
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    # 2. First column: delete every letter of the prefix of word a
    for i in range(len(a) + 1):
        dp[i][0] = i
    # 3. First row: insert every letter of the prefix of word b
    for j in range(len(b) + 1):
        dp[0][j] = j
    # 4. For every other cell, compare the last letters of its two prefixes
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                # 5. Same letter: no edit is needed, so copy the cell up and to the left
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # 6. Different: one edit plus the smallest of three neighboring cells
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    # 7. The bottom right cell turns all of word a into all of word b
    return dp[len(a)][len(b)]

Example 1, traced

Input
a = "horse"
b = "ros"

Output
3

Why it works

Each cell is right if the cells it reads are right. The first row and column are right by counting letters. In any other cell, equal last letters are left alone at no cost, and nothing cheaper exists. Different last letters need a delete, an insert or a replace, and the code takes the cheapest of the three. So every cell is right, the last one included.

Time and space

Time O(n × m), extra space O(n × m). Call the lengths of a and b n and m. The table has (n + 1) × (m + 1) cells, and each is filled once by looking at no more than three cells. That is O(n × m) time, and the table takes O(n × m) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Fill the first row and the first column before the rest. Left at 0, they say an empty word turns into any word for free: turning nothing into abc gives 0 instead of 3, and example 1 gives 2.
• Add 1 only when the last letters differ. If equal letters are charged an edit too, turning same into same costs 4 instead of 0.
• Take the smallest of all three cells. Without the cell up and to the left there is no replace, so swapping a letter costs a delete plus an insert: example 1 gives 4 instead of 3.

Pattern

Two-dimensional dynamic programming. Builds on Longest Common Subsequence.

Keep going