Edit Distance

Medium Problem 130 of 151 Java and Python

Practice on LeetCode

Problem

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

Allowed operations: insert a character, delete a character, replace a character.

Example 1

Input: word1 = "horse", word2 = "ros"
Output: 3
Why: horse → rorse (replace h) → rose (delete r) → ros (delete e).

Example 2

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

Constraints

0 ≤ word1.length, word2.length ≤ 500

Explanation

Look at the last characters. If they match, no operation is needed for them: dist(i - 1, j - 1). Otherwise do one operation: replace (dist(i - 1, j - 1)), delete from word1 (dist(i - 1, j)) or insert into it (dist(i, j - 1)), plus 1.

Base cases: turning i characters into an empty string takes i deletions, and vice versa.

Approach 1 · Naive

Plain recursion

Time O(3^(m + n))
Space O(m + n)

Apply the rule above recursively from the ends of both words.

dist(0, j) = j, dist(i, 0) = i.
Match: dist(i-1, j-1); otherwise 1 + min(dist(i-1, j-1), dist(i-1, j), dist(i, j-1)).

Java

class Solution {
    public int minDistance(String word1, String word2) {
        return dist(word1, word2, word1.length(), word2.length());
    }

    private int dist(String a, String b, int i, int j) {
        if (i == 0) {
            return j;
        }
        if (j == 0) {
            return i;
        }
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            return dist(a, b, i - 1, j - 1);
        }
        return 1 + Math.min(dist(a, b, i - 1, j - 1), Math.min(dist(a, b, i - 1, j), dist(a, b, i, j - 1)));
    }
}

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        def dist(i, j):
            if i == 0:
                return j
            if j == 0:
                return i
            if word1[i - 1] == word2[j - 1]:
                return dist(i - 1, j - 1)
            return 1 + min(dist(i - 1, j - 1), dist(i - 1, j), dist(i, j - 1))

        return dist(len(word1), len(word2))

Approach 2 · Optimal

Bottom-up DP table

Time O(m · n)
Space O(m · n)

Fill dp[i][j] = edit distance between the first i characters of word1 and the first j of word2.

dp[i][0] = i, dp[0][j] = j.
For each cell: if the characters match, copy the diagonal; else 1 + min(diagonal, up, left).
Return dp[m][n].

Java

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int 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];
    }
}

Python

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)]
        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 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], dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]

Complexity compared

Approach	Time	Space
Naive Plain recursion	O(3^(m + n))	O(m + n)
Optimal Bottom-up DP table	O(m · n)	O(m · n)

Key takeaways

Diagonal = replace (or free match), up = delete, left = insert. Draw the table once and it sticks.
This is Levenshtein distance, used in spell checkers and fuzzy search.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem