EDIT Distance

The problem, simply

You get two words, word1 of length m and word2 of length n. You may change word1 one letter at a time, in three ways:

• insert a letter anywhere,
• delete a letter,
• replace a letter with another letter.

Give back the fewest changes needed to make word1 equal to word2.

A story to remember it

Picture it

Examples

Way 1: the simple way

Compare the two words from the front with two fingers, i in word1 and j in word2.

1. If word1 is used up, the rest of word2 must be inserted: n - j changes.
2. If word2 is used up, the rest of word1 must be deleted: m - i changes.
3. If the letters match, move both fingers, no cost.
4. If not, try all three fixes and keep the cheapest, plus 1:
   • delete word1[i]: move i only,
   • insert word2[j]: move j only,
   • replace: move both.

class Solution {
    public int minDistance(String word1, String word2) {
        return solve(word1, word2, 0, 0);
    }

    private int solve(String a, String b, int i, int j) {
        if (i == a.length()) return b.length() - j;   // insert the rest
        if (j == b.length()) return a.length() - i;   // delete the rest
        if (a.charAt(i) == b.charAt(j)) return solve(a, b, i + 1, j + 1);
        int delete  = solve(a, b, i + 1, j);
        int insert  = solve(a, b, i, j + 1);
        int replace = solve(a, b, i + 1, j + 1);
        return 1 + Math.min(delete, Math.min(insert, replace));
    }
}

How long it takes: every mismatch splits into three, and the depth can reach m + n, so O(3^(m+n)). The same (i, j) question is asked again and again. Extra room: the call stack, O(m + n).

Way 2: the clever way

There are only (m + 1) * (n + 1) different questions. Answer each one once and write it in a chart. Let box (i, j) be the fewest changes to turn the first i letters of word1 into the first j letters of word2.

1. Top row: (0, j) = j, because you insert j letters. Left column: (i, 0) = i, because you delete i letters.
2. If letter i of word1 equals letter j of word2: copy the box up and left, (i - 1, j - 1).
3. Otherwise take 1 plus the smallest of three boxes:
   • the box above, (i - 1, j), means delete,
   • the box to the left, (i, j - 1), means insert,
   • the box up and left, (i - 1, j - 1), means replace.
4. The answer is in the bottom right box.

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;   // delete everything
        for (int j = 0; j <= n; j++) dp[0][j] = j;   // insert everything

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];             // same letter, free
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],     // replace
                               Math.min(dp[i - 1][j],             // delete
                                        dp[i][j - 1]));           // insert
                }
            }
        }
        return dp[m][n];
    }
}

How long it takes: (m + 1) * (n + 1) boxes, each in constant time, O(m * n). Extra room: the chart, O(m * n).

Watch out for

• Forgetting the edges. Without dp[i][0] = i and dp[0][j] = j, empty words get cost 0 and every answer is too small.
• When the letters match, do not also add 1 or take a minimum with the others. Copying the diagonal is always at least as good.
• Which box is insert and which is delete is easy to swap. It does not change the number, but it matters if you print the steps.

What interviewers ask next

• Can you use less room? Each row only needs the row above it. Keep two rows, or even one row plus a saved diagonal value, for O(n) room. Put the shorter word on the columns for O(min(m, n)).
• Print the actual changes? Start at the bottom right box and walk back: diagonal on a match, otherwise to whichever neighbor gave the minimum, writing replace, delete or insert as you go.
• What if the three changes have different costs? Use the costs instead of 1 in each choice. The chart works the same way.
• Only inserts and deletes allowed? Then the answer is m + n - 2 * LCS, where LCS is the longest common subsequence. With replace allowed this formula is wrong, because one replace can do the work of a delete plus an insert.
• Is the edit distance within 1 (LeetCode 161)? No chart needed. Walk both words once and allow one difference, O(n).

Remember this

Grown-up words: the fewest changes is the edit distance, also called Levenshtein distance, the chart is a dynamic programming table, answering each question once is memoization or tabulation, and walking back through the chart is reconstructing the solution.