hardDynamic Programming

Edit Distance

Find the fewest single-character insertions, deletions, or replacements needed to transform one word into another.

LeetCode ↗

Work through the cases

3 examples

Input notation

Two lowercase words on separate lines. A line may be empty.

Expected result

The minimum number of edits.

Case 1

Input

cat
cut

Expected output

Case 2

Input

abc

Expected output

Case 3

Input

same
same

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is recursion: at each position of word1 try insert, delete, or replace, then take the best. Correct, but exponential. m,n ≤ 500 needs a polynomial. The bottleneck is overlapping subproblems — converting prefix i into prefix j is solved many times. Let f[i][j] be that minimum. Equal last characters inherit the diagonal; otherwise the three operations map to three neighbors, take \min plus one. Empty-string borders are delete-all / insert-all. The answer is f[m][n].

We define f[i][j] as the minimum number of operations to convert word1 of length i to word2 of length j. f[i][0] = i, f[0][j] = j, i \in [1, m], j \in [0, n].

We consider f[i][j]:

- If word1[i - 1] = word2[j - 1], then we only need to consider the minimum number of operations to convert word1 of length i - 1 to word2 of length j - 1, so f[i][j] = f[i - 1][j - 1]; - Otherwise, we can consider insert, delete, and replace operations, then f[i][j] = \min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1.

Finally, we can get the state transition equation:

f[i][j] = \begin{cases} i, & if j = 0 \\ j, & if i = 0 \\ f[i - 1][j - 1], & if word1[i - 1] = word2[j - 1] \\ \min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1, & otherwise \end{cases}

Finally, we return f[m][n].

The time complexity is O(m × n), and the space complexity is O(m × n). m and n are the lengths of word1 and word2 respectively.

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] f = new int[m + 1][n + 1];
        for (int j = 1; j <= n; ++j) {
            f[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            f[i][0] = i;
            for (int j = 1; j <= n; ++j) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    f[i][j] = Math.min(f[i - 1][j], Math.min(f[i][j - 1], f[i - 1][j - 1])) + 1;
                }
            }
        }
        return f[m][n];
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.