Edit Distance

Given two strings a and b, return the minimum number of operations that convert a into b. The allowed operations on single characters are insert, delete, and replace. This is also called the Levenshtein distance.

LeetCode: 72. Edit Distance

Example

"horse" -> "ros"            ->  3   (replace h with r, delete r, delete e)
"intention" -> "execution"  ->  5

Brute force: recursion on the last characters

Compare the last characters of the first i characters of a and the first j characters of b:

• If they're equal, no operation is needed for them: dist(i - 1, j - 1).
• Otherwise, try all three operations and take the cheapest, plus one:
  • replace a[i-1] with b[j-1]: dist(i - 1, j - 1)
  • delete a[i-1]: dist(i - 1, j)
  • insert b[j-1] at the end of a: dist(i, j - 1)

If one string is empty, the answer is the other string's length.

The recursion takes the lengths i and j of the prefixes, so no substrings are copied.

public class Main {
    static 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)));
    }

    public static void main(String[] args) {
        System.out.println(dist("horse", "ros", 5, 3) + " " + dist("intention", "execution", 9, 9));
    }
}

3 5

Time: O(3^(m+n)): the same pairs of prefixes are solved again and again. Space: O(m + n) for the recursion (each call lowers i, j, or both).

Optimal: a table over prefixes

There are only (m + 1)(n + 1) pairs of prefixes. Let d[i][j] be the distance between the first i characters of a and the first j characters of b, and fill the table row by row; every value depends only on the left, upper, and upper-left neighbours.

Each row needs only the row above it, so two rows are enough.

import java.util.Arrays;

public class Main {
    static int editDistance(String a, String b) {
        int m = a.length(), n = b.length();
        int[] prev = new int[n + 1]; // row for the empty prefix of a
        for (int j = 0; j <= n; j++) prev[j] = j;
        for (int i = 1; i <= m; i++) {
            int[] cur = new int[n + 1];
            Arrays.fill(cur, i);
            for (int j = 1; j <= n; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    cur[j] = prev[j - 1];
                } else {
                    cur[j] = 1 + Math.min(prev[j - 1], Math.min(prev[j], cur[j - 1]));
                }
            }
            prev = cur;
        }
        return prev[n];
    }

    public static void main(String[] args) {
        System.out.println(editDistance("horse", "ros") + " " + editDistance("intention", "execution"));
        System.out.println(editDistance("", "abc") + " " + editDistance("same", "same"));
    }
}

3 5
3 0

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

cur[0] = i (the Arrays.fill value) is the cost of deleting all i characters of a[..i]. The other initial values are overwritten.

Edge cases

• An empty string: the distance is the other string's length.
• Equal strings: 0.
• Unicode: charAt returns 16-bit UTF-16 code units. Characters outside the Basic Multilingual Plane (such as many emoji) take two units and count as two. Convert with codePoints().toArray() to compare whole characters.