Edit Distance

medium2D Dynamic Programming82 stepsJava · Python · C++

Minimum inserts, deletes and replacements to turn word1 into word2. dp[i][j] = cost for the first i and j characters. Equal characters cost nothing extra (diagonal); otherwise 1 + the best of replace (diagonal), delete (up) or insert (left).

▶ Watch the animated trace

Traced input: word1 = "horse", word2 = "ros" → 3. Original problem: neetcode.io/problems/edit-distance

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(m·n)

Two rows are enough for the length only.

Key idea

Row 0: building word2[0..j) from nothing takes j inserts. Column 0: i deletes.
Match: dp[i][j] = dp[i−1][j−1].
Otherwise 1 + min(replace, delete, insert).

Common mistakes

Mixing up which neighbour means insert vs delete (they're symmetric, so the answer survives, but the explanation doesn't).
Forgetting the base row and column.

Solution

Java

int minDistance(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
            }
        }
    }
    return dp[m][n];
}

Python

def minDistance(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i
    for j in range(n + 1): dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[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])
    return dp[m][n]

C++

int minDistance(string a, string b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i - 1] == b[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]});
            }
        }
    }
    return dp[m][n];
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Empty source Three inserts.	`word1 = "", word2 = "abc"`	`3`
Identical Nothing to change.	`word1 = "same", word2 = "same"`	`0`
Completely different Three replacements.	`word1 = "abc", word2 = "xyz"`	`3`