Edit Distance

MediumDynamic Programming (1-D & 2-D)NeetCode 150MidOpen on LeetCodeUpdated Sep 21, 2026

You're given two strings word1 and word2. Return the minimum number of operations needed to turn word1 into word2. One operation is inserting a single character anywhere, deleting a single character, or replacing one character with a different one, and each costs 1. Characters that already line up cost nothing, so equal strings need 0 operations, and turning a string into the empty string takes one delete per character.

Examples

word1 = "horse", word2 = "ros" returns 3

Replace "h" with "r" (rorse), delete the second "r" (rose), then delete "e" (ros). Two operations would both have to be deletes, and deleting any two letters of "horse" never leaves "ros".

word1 = "intention", word2 = "execution" returns 5

Delete "t" (inention), replace "i" with "e" (enention), replace "n" with "x" (exention), replace "n" with "c" (exection), then insert "u" (execution).

word1 = "", word2 = "abc" returns 3

Starting from the empty string, insert "a", "b" and "c": one operation per character.

Constraints

0 <= word1.length, word2.length <= 500
word1 and word2 consist of lowercase English letters.

Hints

Hint 1

Look at the last character of each string. If they match, what's left to fix? If they don't, what could the final operation have been?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Let dp[i][j] be the fewest operations that turn the first i characters of word1 into the first j of word2. Row 0 is 0..n (all inserts) and column 0 is 0..m (all deletes). If word1[i-1] == word2[j-1] the last characters line up for free, so dp[i][j] = dp[i-1][j-1]; otherwise dp[i][j] = 1 + min(dp[i-1][j-1] for replace, dp[i-1][j] for delete, dp[i][j-1] for insert). O(m * n) time and space for lengths m and n.

Time

O(m * n)

Space

O(m * n)

Pitfall

Leaving the base row and column at 0. Turning a prefix of length i into the empty string costs i deletes, not 0, and zero seeds make "abc" vs "" return 0.

Solutions

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1]; // dp[i][j]: word1[0..i) -> word2[0..j)
        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];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],         // replace
                            Math.min(dp[i - 1][j], dp[i][j - 1])); // delete, insert
                }
            }
        }
        return dp[m][n];
    }
}

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)]  # dp[i][j]: word1[:i] -> word2[:j]
        for i in range(m + 1):
            dp[i][0] = i  # delete everything
        for j in range(n + 1):
            dp[0][j] = j  # insert everything
        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 from word1
                        dp[i][j - 1],      # insert into word1
                    )
        return dp[m][n]