Edit Distance

Problem in plain words

You want to turn word1 into word2. One operation lets you insert a character, delete a character, or replace one character with another. Return the fewest operations needed.

For example, "cat" becomes "cut" with one replacement, and "cat" becomes "cast" with one insertion.

Intuition

Work with prefixes. Look at the last character of each prefix. If they match, nothing needs to be done for them, so the cost is the same as for both prefixes without that character. If they differ, the last operation was one of three things: replace the last character of word1 (diagonal), delete it (move up a row), or insert the last character of word2 (move left a column). Take the cheapest and add 1. The table is shaped exactly like the one in the LCS lesson; only the rule inside each cell changes.

Approach

1. State: dp[i][j] is the edit distance between the first i characters of word1 and the first j characters of word2.
2. Recurrence: if word1[i - 1] == word2[j - 1], dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]).
3. Base cases: dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything).
4. Order: rows top to bottom, columns left to right. Return dp[m][n].

Dry run

Input: word1 = "abc", word2 = "yabd". Rows are prefixes of word1.

The answer is 2: insert y at the front and replace c with d.

Java solution

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 all
        for (int j = 0; j <= n; j++) dp[0][j] = j;   // insert all

        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];
                } else {
                    int replace = dp[i - 1][j - 1];
                    int delete = dp[i - 1][j];
                    int insert = dp[i][j - 1];
                    dp[i][j] = 1 + Math.min(replace, Math.min(delete, insert));
                }
            }
        }
        return dp[m][n];
    }
}

Python solution

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i          # delete all
        for j in range(n + 1):
            dp[0][j] = j          # insert all
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j - 1],   # replace
                                       dp[i - 1][j],       # delete
                                       dp[i][j - 1])       # insert
        return dp[m][n]

Complexity

Edge cases and common mistakes

• One empty string: the answer is the other string's length, which the base row and column already give.
• Identical strings: every diagonal is a match and the answer is 0.
• Adding 1 on a match: a match costs nothing; only mismatches add an operation.
• Forgetting the base row/column: leaving them at 0 claims that turning "abc" into "" is free.