Course4all
Join us on telegram
Home/dsa/Dynamic Programming/Edit Distance

Edit Distance

Master this topic with zero to advance depth.

Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character

Visual Representation

word1 = "horse", word2 = "ros" Steps: 1. horse -> rorse (replace 'h' with 'r') 2. rorse -> rose (remove 'r') 3. rose -> ros (remove 'e') Result: 3 DP Strategy: dp[i][j] = min distance between word1[0...i] and word2[0...j]
Hard

Examples

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

horse -> rorse (replace 'h' with 'r') -> rose (remove 'r') -> ros (remove 'e')

Input: word1 = "intention", word2 = "execution"
Output: 5
Approach 1

Level I: Dynamic Programming (2D)

Intuition

We build a 2D table where dp[i][j] is the minimum operations to convert word1[0...i] to word2[0...j].

Thought Process

  1. If word1[i-1] == word2[j-1], no operation is needed for the current character: dp[i][j] = dp[i-1][j-1].
  2. If they are different, we take the minimum of three operations:
    • Insert: 1 + dp[i][j-1]
    • Delete: 1 + dp[i-1][j]
    • Replace: 1 + dp[i-1][j-1]
  3. Base cases: Converting string to empty string requires i (or j) deletions.
⏱ O(N * M)💾 O(N * M)

Detailed Dry Run

word1 = "abc", word2 = "abd"

i\j""'a''b''d'
""0123
'a'10 (match)12
'b'210 (match)1
'c'3211 (replace 'c' with 'd')
java
public class Main {
    public static 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;
        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 (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], Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros")); // 3
    }
}
Approach 2

Level II: Memoization (Top-Down 2D)

Intuition

The recursive brute force for edit distance has overlapping subproblems (i, j). Cache results to avoid recomputation.

Visual

word1='horse', word2='ros' solve(0,0): 'h'!='r' -> min(solve(1,1), solve(1,0), solve(0,1)) solve(1,1): cached after first call!
⏱ O(M * N)💾 O(M * N)

Detailed Dry Run

word1="ab", word2="a". solve(0,0): 'a'=='a' -> solve(1,1). solve(1,1): 'b'!='', return 1+solve(2,1)=1.

java
import java.util.Arrays;

public class Main {
    static int[][] memo;
    public static int solve(String w1, String w2, int i, int j) {
        if (i == w1.length()) return w2.length() - j;
        if (j == w2.length()) return w1.length() - i;
        if (memo[i][j] != -1) return memo[i][j];
        if (w1.charAt(i) == w2.charAt(j)) return memo[i][j] = solve(w1, w2, i+1, j+1);
        return memo[i][j] = 1 + Math.min(solve(w1, w2, i+1, j+1),
            Math.min(solve(w1, w2, i+1, j), solve(w1, w2, i, j+1)));
    }

    public static int minDistance(String word1, String word2) {
        memo = new int[word1.length()][word2.length()];
        for (int[] r : memo) Arrays.fill(r, -1);
        return solve(word1, word2, 0, 0);
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros")); // 3
    }
}
Approach 3

Level III: Space Optimized (1D)

Intuition

To compute dp[i][j], we only need the current row and the previous row. Specifically, dp[i-1][j-1] (diagonal), dp[i-1][j] (up), and dp[i][j-1] (left).

Logic Steps

  1. Initialize curr array of size n+1 with base case values 0...n.
  2. Iterate through word1. For each i:
    • Cache dp[i-1][j-1] in a prev variable.
    • Update the curr[0] for the base case (conversions from word1[0...i] to empty string).
    • Inner loop through word2 to update curr[j].
  3. Return curr[n].
⏱ O(N * M)💾 O(Min(N, M))

Detailed Dry Run

word1 = "abc", word2 = "abd" Focus on space reduction where we store only 1 row. Diag (prev) cache is critical to keep the value from the 'upper-left' cell before it was overwritten.

java
public class Main {
    public static int minDistance(String word1, String word2) {
        int n = word2.length();
        int[] dp = new int[n + 1];
        for (int j = 0; j <= n; j++) dp[j] = j;

        for (int i = 1; i <= word1.length(); i++) {
            int prev = dp[0];
            dp[0] = i;
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[j] = prev;
                } else {
                    dp[j] = 1 + Math.min(prev, Math.min(dp[j], dp[j - 1]));
                }
                prev = temp;
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("abc", "abd")); // 1
    }
}
← Previous QuestionLongest Valid Parentheses
Next Question →Frog Jump