Edit Distance

The problem, simply

You get two words, word1 and word2. In one step you can do one of these to word1:

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

Give back the smallest number of steps that turns word1 into word2.

A story to remember it

Picture it

Examples

Way 1: the simple way

Let dist(i, j) be the answer for the first i letters of word1 and the first j letters of word2.

1. If i == 0, insert all j letters: return j. If j == 0, delete all i letters: return i.
2. If the last letters match, they need no step: return dist(i - 1, j - 1).
3. Otherwise try all three fixes and keep the cheapest, plus 1 for the step itself:
   • replace: dist(i - 1, j - 1),
   • delete the last letter of word1: dist(i - 1, j),
   • insert the last letter of word2: dist(i, j - 1).

class Solution {
    int dist(String a, String b, int i, int j) {
        if (i == 0) return j;                       // insert the rest of b
        if (j == 0) return i;                       // delete the rest of a
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            return dist(a, b, i - 1, j - 1);        // last letters match: free
        }
        int replace = dist(a, b, i - 1, j - 1);
        int delete = dist(a, b, i - 1, j);
        int insert = dist(a, b, i, j - 1);
        return 1 + Math.min(replace, Math.min(delete, insert));
    }

    public int editDistance(String word1, String word2) {
        return dist(word1, word2, word1.length(), word2.length());
    }
}

How long it takes: each call can make three calls, and the calls go m + n deep, O(3^(m+n)). Extra room: the chain of waiting calls, O(m + n).

Way 2: the clever way

There are only (m + 1) * (n + 1) different pairs (i, j). Put them in a table dp and fill it row by row, left to right. When we reach a box, the boxes above, to the left and up-left are already done.

1. dp[i][0] = i and dp[0][j] = j.
2. If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1].
3. Else dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
4. The answer is dp[m][n].

Up-left is replace, up is delete, left is insert.

class Solution {
    public int editDistance(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];     // match: no step
                } 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: one quick step per box, O(m * n). Extra room: the table, O(m * n). Each row only uses the row above, so two rows (or one row and a saved number) bring it down to O(min(m, n)).

Watch out for

• Forgetting the first row and column. Without them every box reads zeros and the answer comes out too small.
• When the letters match, take dp[i-1][j-1] with no + 1. Taking the min of all three there is still correct, but adding 1 to it is not.
• One empty word: the answer is the length of the other word.

What interviewers ask next

• Print the actual steps. Start at the bottom right and walk back along the arrows that gave each minimum, as in the last frame above.
• Steps have different prices (insert costs 2, delete 3, replace 4)? Use those prices instead of + 1. The table is the same.
• Only insert and delete allowed? Then the answer is m + n - 2 * LCS, where LCS is the longest common subsequence.
• Are two words at most one edit apart? You do not need a table: walk both words with two pointers and allow one mismatch, O(m + n).
• Swapping two neighboring letters counts as one step? That is the Damerau distance. Add one more case that looks two rows and two columns back.

Remember this

Grown-up words: the number of steps is the edit distance (also called Levenshtein distance), the chart is a 2D DP table, the three fixes are the transitions, and walking back along the arrows is backtracking to rebuild the answer.