Edit Distance

Question (LC.72)

Given two strings, find the minimum number of edits to transform string1 to string2.

Example

I: "Saturday", "Sunday"
O: 4
I: "More", "Less"

Brute Force Search

The most brute force search is just to enumerate all the possible matches for #edits = 1, 2, 3, ..., n until we find a match. Or we can do a smarter search that starts either from the beginning or the end, comparing the corresponding characters.

If we start from the beginning, then the minimum number of edits for s1 to match s2

if s1[m] == s2[n]
    return editDistance(s1, s2, m+1, n+1)
else
    return 1 + Math.min(
        editDistance(s1, s2, m, n + 1), // insertion
        editDistance(s1, s2, m + 1, n), // deletion
        editDistance(s1, s2, m + 1, n + 1)  // substitution
    ) ;

The recurrence above should capture all the possibilities. Inside the else statement, the presumed equivalent cost of edit 1 + the min of the rest is guaranteed to be optimal. What if spending one edit is actually more cost efficient then having a match in the if statement? We can get a formal proof by reordering steps in an arbitrary optimum solution. But this example should give some good intuition. Consider SabSunday and Sunday. If we match the S in the beginning, we just have to delete the second S when we get there. The minimum number of edits still remain as 3.

Brute Force Code

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

private int editDistance(String s1, String s2, int m, int n) {
    // base case reach the end
    if (m == s1.length()) {
        // insert the rest of s2
        return s2.length() - n;
    }
    if (n == s2.length()) {
        // delete the rest of s1
        return s1.length() - m;
    }
    // search and return
    if (s1.charAt(m) == s2.charAt(n)) {
        return editDistance(s1, s2, m + 1, n + 1);
    } else {
        return 1 + minAdv(
            editDistance(s1, s2, m, n + 1), // insertion
            editDistance(s1, s2, m + 1, n), // deletion
            editDistance(s1, s2, m + 1, n + 1) // substitution
        );
    }
}

private int minAdv(int num1, int num2, int num3) {
    return Math.min(Math.min(num1, num2), num3);
}

Search works. The exponential time complexity doesn't. A relative short example like dinitrophenylhydrazine and acetylphenylhydrazine will give Time Limit Exceeded. See the induction proof in Rod Cutting.

Bottom Up DP

Observe the recursion for the following example

If we define a subproblem as ED(i,j), then ED(i,j) represents the optimal solution at using the suffix s1[i:m] to fully match the suffix s2[j:n]. From the recursion tree, we can find quite a few subtrees can be reused if they are memoized. Dynamic programming is the way to go.

Solve by Suffix

1. Define optimal subproblems
ED(i,j) = minimum number of edits for A[i:m] to fully match B[j:n]

2. Solve by suffix
if (A[i] == B[j])
    ED(i,j) = ED(i+1,j+1)
else
    ED(i,j) = 1 + Math.min(
        ED(i,j+1),
        ED(i+1,j),
        ED(i+1,j+1)
    )

3. Topo order
from small suffixes to the beginning
fill in col by col from right to left
for j from n-1 to 0
    for i from m-1 to 0

4. Init base
last row and last col
for i from m to 0
    ED(i,n) = m - i
for j from n to 0
    ED(m,j) = n - j

5. Final answer
ED(0,0)

public int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    char[] A = s1.toCharArray(), B = s2.toCharArray();
    // create memo table
    int[][] ED = new int[m + 1][n + 1];
    // init base case
    for (int i = m; i >= 0; i--) {
        ED[i][n] = m - i; // last col
    }
    for (int j = n; j >= 0; j--) {
        ED[m][j] = n - j; // last row
    }
    // topo order
    for (int j = n - 1; j >= 0; j--) {
        for (int i = m - 1; i >= 0; i--) {
            if (A[i] == B[j]) {
                ED[i][j] = ED[i+1][j+1];
            } else {
                ED[i][j] = 1 + minAdv(
                    ED[i][j+1], // insert
                    ED[i+1][j], // delete
                    ED[i+1][j+1] // substitute
                );
            }
        }
    }
    // final answer
    return ED[0][0];
}

Solve by Prefix

Defining the subproblem by prefix might be easier to write sometimes.

1. Define optimal subproblem
ED(i,j) = minimum number of edits for A[0:i] to fully match B[0:j]

2. Solve by prefix
if A[i] == B[j]
    ED(i,j) = ED(i-1,j-1)
else
    ED(i,j) = 1 + advMin(
        ED(i,j-1), // insert
        ED(i-1, j), // delete
        ED(i-1,j-1) // substitute
    )

3. Init base case
for i from 0 to m
    ED(i,0) = i // first col
for j from 0 to n
    ED(0,j) = j // first row

4. Topo Order
row by row from left to right
for i from 1 to m
    for j from 1 to n

5. Final answer
ED(m,n)

public int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    // create memo table
    int[][] memo = new int[m+1][n+1];
    // init base case
    for (int i = 0; i <= m; i++) {
        memo[i][0] = i; // first col
    }
    for (int j = 0; j <= n; j++) {
        memo[0][j] = j; // first row
    }
    // topo order
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                memo[i][j] = memo[i-1][j-1];
            } else {
                memo[i][j] = 1 + minAdv(
                    memo[i][j-1], // insert
                    memo[i-1][j], // delete
                    memo[i-1][j-1] // substitute
                );
            }
        }
    }
    // final answer
    return memo[m][n];
}

Prefix vs Suffix

The tabulation process for prefix is going down (removing from the end so tabulate down) and for suffix is going up (removing from the beginning so tabulate up).

By Prefix	By Suffix

Time & Space Complexity

Time is O(m*n) but space is trickier. We are using O(m*n) space right now for better understanding. But we can get to constant space with careful implementation since the dependencies are only two layers.