Edit Distance

Medium20–25 min

Topics

Dynamic ProgrammingString

Companies

GoogleAmazonMicrosoft

Given two lowercase words, find the fewest single-character edits — inserting, deleting, or swapping one character for another — needed to turn the first word into the second. Every partial answer only depends on smaller versions of the same question: how many edits does it take to turn some prefix of word1 into some prefix of word2? Once the last pair of letters is decided — either they already agree and cost nothing, or one of the three edits has to cover the mismatch — what's left is exactly the same problem on shorter prefixes. Solving every prefix pair once, smallest first, and reading off three already-known neighbors for each new cell turns an otherwise exponential search into a single pass over a grid.

Test Case 1:

Input:word1 = "horse", word2 = "ros"

Output:3

Explanation:One 3-move path: replace 'h' with 'r' ("horse" → "rorse"), delete the second 'r' ("rorse" → "rose"), then delete the trailing 'e' ("rose" → "ros"). Other 3-move sequences exist too, but none can do it in fewer edits.

Test Case 2:

Input:word1 = "abc", word2 = "abc"

Output:0

Explanation:Identical strings need zero edits — every character already lines up.

Test Case 3:

Input:word1 = "", word2 = "abc"

Output:3

Explanation:word1 is empty, so the only option is inserting all three characters of word2 one at a time.

Constraints

◆0 ≤ word1.length, word2.length ≤ 10
◆word1 and word2 consist of lowercase English letters

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Walk both words from their ends inward. If the current last characters already match, that pair is free — shrink both words by one and move on. If they don't match, one of the three edits has to happen right here: drop word1's last character (delete), tack on word2's last character (insert), or swap word1's last character for word2's (replace) — each of those turns into a smaller version of the exact same question, so try all three and keep whichever leads to the fewest total edits, adding 1 for the move just made. Nothing here is cached, so the same (i, j) pair of remaining lengths gets re-solved every time a different sequence of edits happens to land on it.

TimeO(3^(n+m))

SpaceO(n+m)

Java

Try it out

class Solution {
    private String word1, word2;

    public int minDistance(String word1, String word2) {
        this.word1 = word1;
        this.word2 = word2;
        return solve(word1.length(), word2.length());
    }

    private int solve(int i, int j) {
        if (i == 0) return j;
        if (j == 0) return i;
        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
            return solve(i - 1, j - 1);
        }
        int insertOp = solve(i, j - 1);
        int deleteOp = solve(i - 1, j);
        int replaceOp = solve(i - 1, j - 1);
        return 1 + Math.min(insertOp, Math.min(deleteOp, replaceOp));
    }
}

Optimal — Bottom-Up 2D DP

Optimal

Build a grid where cell (i, j) holds the answer for turning the first i characters of word1 into the first j characters of word2. The two edges of the grid are free: turning an empty word1 into j characters costs j inserts, and turning i characters into an empty word2 costs i deletes. Every other cell reads off three already-solved neighbors — the one diagonally up-left, the one directly above, and the one directly to the left — since those correspond exactly to the replace, delete, and insert options. When the two current characters already match, the diagonal neighbor's value carries over untouched, no edit spent. Filling the grid row by row means every smaller sub-problem is computed exactly once before it's needed.

TimeO(n·m)

SpaceO(n·m)