☕ DSA Java Articles

Topics › Dynamic Programming › DP on Strings

Edit distance

Hard TUF ID 307 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given two strings s1 and s2, return the minimum number of operations needed to turn s1 into s2. Each operation acts on a single character of s1:

This number is also called the Levenshtein distance. It is what spell checkers and diff-like tools use to measure how far apart two words are.

Constraints (LeetCode 72): 0 ≤ |s1|, |s2| ≤ 500, lowercase English letters.

Example 1

s1 = "horse", s2 = "ros"
answer = 3          // horse -> rorse (replace h with r) -> rose (delete r) -> ros (delete e)

Example 2

s1 = "intention", s2 = "execution"
answer = 5          // e.g. delete t, replace i->e, replace n->x, replace n->c, insert u

Thinking about the last characters

Write f(i, j) for the fewest operations that turn the prefix s1[0..i) into the prefix s2[0..j). Prefix lengths make the base cases easy to state:

These base cases are not zero, which is the first thing that sets this problem apart from LCS.

For i, j > 0, picture the final alignment of the two strings: every character of s1 is either kept (possibly replaced) as some character of s2, or deleted, and every character of s2 not produced that way was inserted. Look at what happens to the last characters, s1[i - 1] and s2[j - 1]:

  1. s1[i - 1] becomes s2[j - 1]. If they are already equal this costs nothing, otherwise it is one replacement. Either way the rest of the problem is f(i - 1, j - 1).
  2. s1[i - 1] is deleted. One operation, and we still have to turn s1[0..i - 1) into all of s2[0..j): 1 + f(i - 1, j).
  3. s2[j - 1] is inserted at the end. One operation, and s1[0..i) still has to become s2[0..j - 1): 1 + f(i, j - 1).

Every optimal edit script falls into one of these cases, so the minimum over them is the answer.

Why a match never needs the other two options. When s1[i - 1] == s2[j - 1], the code takes f(i - 1, j - 1) without looking at insert or delete. That is safe because adding or removing one character from either string changes the distance by at most one, so f(i - 1, j - 1) ≤ f(i - 1, j) + 1 and f(i - 1, j - 1) ≤ f(i, j - 1) + 1. The free diagonal move is never worse than paying for a delete or an insert.

So the recurrence is:

f(i, j) = f(i - 1, j - 1)                                         if s1[i - 1] == s2[j - 1]
f(i, j) = 1 + min(f(i, j - 1), f(i - 1, j), f(i - 1, j - 1))      otherwise
                  insert       delete       replace

A useful way to remember the directions: insert shrinks s2 (we produced its last character), delete shrinks s1 (we removed its last character), replace shrinks both.

Approach 1: Recursion

Intuition. Code the recurrence directly. When the last characters disagree, try all three operations and keep the cheapest.

Algorithm.

  1. If i == 0, return j. If j == 0, return i.
  2. If s1[i - 1] == s2[j - 1], return f(i - 1, j - 1).
  3. Otherwise return 1 + min(f(i, j - 1), f(i - 1, j), f(i - 1, j - 1)).
static int recursive(String s1, String s2) {
    return solve(s1.length(), s2.length(), s1, s2);
}

/** Fewest operations that turn s1[0..i) into s2[0..j). */
static int solve(int i, int j, String s1, String s2) {
    if (i == 0) return j;                                    // insert the j remaining characters of s2
    if (j == 0) return i;                                    // delete the i remaining characters of s1
    if (s1.charAt(i - 1) == s2.charAt(j - 1)) return solve(i - 1, j - 1, s1, s2);   // last characters agree: free
    int insert = solve(i, j - 1, s1, s2);                    // append s2[j - 1]; s2 shrinks
    int delete = solve(i - 1, j, s1, s2);                    // remove s1[i - 1]; s1 shrinks
    int replace = solve(i - 1, j - 1, s1, s2);               // overwrite s1[i - 1] with s2[j - 1]; both shrink
    return 1 + Math.min(insert, Math.min(delete, replace));
}

Complexity. Time O(3^(n + m)) in the worst case: when no characters match, each call branches three ways and the depth can reach n + m. Space O(n + m) for the recursion stack.

Approach 2: Memoization

Intuition. Only (n + 1)(m + 1) distinct pairs (i, j) exist, and the three branches overlap heavily: “delete then insert” and “insert then delete” both reach f(i - 1, j - 1), as does a single replace. Caching every state in dp[i][j] removes all of that repeated work. The sentinel is -1, because a distance of 0 is a real answer.

Algorithm.

  1. Create dp[n + 1][m + 1] filled with -1.
  2. Run the recursion, returning dp[i][j] if it is set, and storing each result before returning it.
static int memoization(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(n, m, s1, s2, dp);
}

static int memo(int i, int j, String s1, String s2, int[][] dp) {
    if (i == 0) return j;
    if (j == 0) return i;
    if (dp[i][j] != -1) return dp[i][j];
    if (s1.charAt(i - 1) == s2.charAt(j - 1)) return dp[i][j] = memo(i - 1, j - 1, s1, s2, dp);
    int insert = memo(i, j - 1, s1, s2, dp);
    int delete = memo(i - 1, j, s1, s2, dp);
    int replace = memo(i - 1, j - 1, s1, s2, dp);
    return dp[i][j] = 1 + Math.min(insert, Math.min(delete, replace));
}

Complexity. Time O(n · m): each state is computed once with constant work. Space O(n · m) for the table plus O(n + m) stack, which for 500-character strings is about 1000 frames.

Approach 3: Tabulation

Intuition. Each cell depends on the cell to its left (insert), the cell above (delete) and the cell above-left (replace or match). Filling row by row, left to right, makes all three available. Row 0 is 0, 1, …, m and column 0 is 0, 1, …, n, straight from the base cases.

Algorithm.

  1. Create dp[n + 1][m + 1]. Set dp[i][0] = i and dp[0][j] = j.
  2. For i = 1 .. n, j = 1 .. m: copy the diagonal on a match, otherwise take 1 + the minimum of left, above and diagonal.
  3. Return dp[n][m].
static int tabulation(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
        }
    }
    return dp[n][m];
}

Dry run on Example 1 (s1 = "horse" down the side, s2 = "ros" across):

  ”” r o s
”” 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3

Bold cells are matches, each copying its upper-left neighbour. For instance dp[2][2] = dp[1][1] = 1: turning ho into ro costs the same as turning h into r, one replacement. The final cell dp[5][3] = 3 comes from the cell above (dp[4][3] = 2, turning hors into ros) plus one deletion of e. Following the cheapest choices back from the corner recovers an actual edit script.

Complexity. Time O(n · m), space O(n · m).

Approach 4: Space optimized

Intuition. Row i reads only row i - 1 and the part of row i already filled. Keep two arrays, prev for row i - 1 and cur for row i, and swap them after each row. The one thing to remember is the base case of each new row: cur[0] must be set to i (delete all i characters). Because the arrays are swapped and reused, cur[0] would otherwise hold a stale value from two rows ago.

Algorithm.

  1. prev[j] = j for every j (row 0).
  2. For each i = 1 .. n: set cur[0] = i, fill cur[1..m] from prev and cur, then swap prev and cur.
  3. After the last swap prev holds row n; return prev[m].
static int spaceOptimized(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[] prev = new int[m + 1], cur = new int[m + 1];
    for (int j = 0; j <= m; j++) prev[j] = j;
    for (int i = 1; i <= n; i++) {
        cur[0] = i;
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) cur[j] = prev[j - 1];
            else cur[j] = 1 + Math.min(cur[j - 1], Math.min(prev[j], prev[j - 1]));
        }
        int[] tmp = prev; prev = cur; cur = tmp;
    }
    return prev[m];
}

Complexity. Time O(n · m), space O(m). Passing the shorter string as s2 gives O(min(n, m)); this is safe because edit distance is symmetric (swap the roles of insert and delete).

Edge cases and pitfalls