Edit Distance

NeetCode: Edit Distance · LeetCode: 72. Edit Distance · Difficulty: Medium

Given two strings word1 and word2 (Java Strings), return the minimum number of operations to convert word1 into word2. The allowed operations are inserting a character, deleting a character and replacing a character.

Example

Text

Input:  word1 = "horse",     word2 = "ros"          Output: 3
Input:  word1 = "intention", word2 = "execution"    Output: 5

Brute force: try every operation

Compare the first characters of the two remaining suffixes. If they match, no operation is needed there, so move both forward. Otherwise pay 1 and try all three operations: delete from word1 (advance i), insert into word1 (advance j), or replace (advance both), keeping the cheapest. When one string is used up, the other's remaining length is the cost. Three branches on mismatches gives exponential time, with many repeated suffix pairs.

Java

class Solution {
    private int dist(String a, String b, int i, int j) {
        if (i == a.length()) {
            return b.length() - j;
        }
        if (j == b.length()) {
            return a.length() - i;
        }
        if (a.charAt(i) == b.charAt(j)) {
            return dist(a, b, i + 1, j + 1);
        }
        int delete = dist(a, b, i + 1, j);
        int insert = dist(a, b, i, j + 1);
        int replace = dist(a, b, i + 1, j + 1);
        return 1 + Math.min(delete, Math.min(insert, replace));
    }

    public int minDistance(String word1, String word2) {
        return dist(word1, word2, 0, 0);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minDistance("horse", "ros"));
        System.out.println(sol.minDistance("intention", "execution"));
        System.out.println(sol.minDistance("", "abc"));
        System.out.println(sol.minDistance("abc", ""));
        System.out.println(sol.minDistance("", ""));
    }
}

Output

Time: O(3^(m+n)) in the worst case. Space: O(m + n).

Better: 2D table

dp[i][j] is the edit distance between the first i characters of word1 and the first j of word2. The borders are the cost of building a prefix from nothing: dp[i][0] = i deletions and dp[0][j] = j insertions. Inside, equal characters cost nothing (dp[i-1][j-1]); otherwise take 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), i.e. delete, insert or replace.

Java

class Solution {
    public 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], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                }
            }
        }
        return dp[m][n];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minDistance("horse", "ros"));
        System.out.println(sol.minDistance("intention", "execution"));
        System.out.println(sol.minDistance("", "abc"));
        System.out.println(sol.minDistance("abc", ""));
        System.out.println(sol.minDistance("", ""));
    }
}

Output

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

Optimal: one rolling row

Each cell reads its upper, left and upper-left neighbours. Keep one row; before overwriting row[j] it holds the upper value, row[j - 1] is the new left value, and the upper-left value is saved in a temporary diag before it is overwritten.

Java

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[] row = new int[n + 1];
        for (int j = 0; j <= n; j++) {
            row[j] = j;
        }
        for (int i = 1; i <= m; i++) {
            int diag = row[0]; // dp[i-1][j-1]
            row[0] = i;
            for (int j = 1; j <= n; j++) {
                int up = row[j]; // dp[i-1][j]
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    row[j] = diag;
                } else {
                    row[j] = 1 + Math.min(up, Math.min(row[j - 1], diag));
                }
                diag = up;
            }
        }
        return row[n];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.minDistance("horse", "ros"));
        System.out.println(sol.minDistance("intention", "execution"));
        System.out.println(sol.minDistance("", "abc"));
        System.out.println(sol.minDistance("abc", ""));
        System.out.println(sol.minDistance("", ""));
    }
}

Output

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