Classic Dynamic Programming: Edit Distance - LeetCode by Example

Today’s problem: LeetCode 72. Edit Distance (Hard)

Given two strings s and t, convert s into t. You can perform three operations: insert a character, delete a character, or replace a character. Calculate the minimum number of operations required to convert s into t.

Example:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
    horse -> rorse (replace 'h' with 'r')
    rorse -> rose (delete 'r')
    rose -> ros (delete 'e')

Today we’ll discuss a classic two-dimensional dynamic programming problem: Edit Distance.

You’ve probably heard of “edit distance” in various contexts. Edit distance, also known as Levenshtein distance, measures the degree of difference between two strings. It’s used in applications like spell checking and text diffing. The practical significance of the edit distance problem makes it a favorite among interviewers.

The edit distance problem is a LeetCode Hard problem. Many people find it very challenging and struggle to come up with an approach. The difficulty mainly lies in two aspects:

First, how to recognize that dynamic programming can be used when you first see the problem. This typically requires familiarity with classic 2D dynamic programming examples, which then helps you draw connections to this problem.
Second, how to break down the problem description into a concrete dynamic programming approach. This requires certain techniques for decomposing DP problems.

In today’s article, we’ll use the edit distance problem as an example to discuss how to tackle these two difficulties of dynamic programming. We’ll first talk about how to decompose a complex problem into a DP approach, and then discuss how to draw connections between different DP problems.

Breaking Down Edit Distance

Suppose you already know that edit distance is solved using dynamic programming. How do you work out the specific approach?

We all know the steps for solving DP problems: first define subproblems, then write the recurrence relation. We understand the theory, but for a specific problem, defining the subproblems and their recurrence relation still requires considerable skill.

If you look at edit distance from a high level, it’s actually hard to get started. How exactly should you combine insert, delete, and replace operations to achieve the minimum number of edits? What properties do these operations satisfy?

When working on DP problems, if you find it difficult to think from the global perspective, try setting aside the big picture and starting from a local perspective. We can focus on just “one step,” and leave the remaining steps for other subproblems to handle. For edit distance, this “one step” refers to a “single edit operation.”

Let’s use “horse” and “ros” as an example. We consider whether this “one step” is an insert, delete, or replace operation.

If we perform an insert, we insert ‘s’ at the end of “ros”, and we still need to compute the edit distance from “horse” to “ro”;
If we perform a delete, we delete ‘e’ at the end of “horse”, and we still need to compute the edit distance from “hors” to “ros”;
If we perform a replace, we replace ‘e’ at the end of “horse” with ‘s’ at the end of “ros”, and we still need to compute the edit distance from “hors” to “ro”.

Why focus on “one step”? Because the key to dynamic programming lies in finding the “recurrence relation between subproblems,” also called the “state transition equation.” A “recurrence relation” describes how one subproblem can be transformed into another through a “single step” operation.

For example, in the House Robber problem we discussed before, when computing subproblem $f(k)$ , we have two choices: $f(k)$ is computed from $f(k-1)$ , or $f(k)$ is computed from $f(k-2)$ . In other words, subproblem $f(k)$ can be transformed into $f(k-1)$ or $f(k-2)$ .

This is similar to a recursive approach. I only need to handle the current step correctly, and trust that the recursive function will take care of the rest. Dynamic programming is actually quite similar to recursion, except that DP typically computes bottom-up and saves each subproblem.

For the edit distance problem, our “one step” has three “choices.” By choosing insert, delete, or replace, we can transform the current subproblem into different subproblems:

Transforming the current subproblem into different subproblems

This makes it quite clear how to define subproblems for edit distance. Different subproblems simply correspond to different lengths of s and t. We can define subproblem $f(i, j)$ as “the edit distance between s[0..i) and t[0..j).” The recurrence relation then has three branches, corresponding to the three operations: insert, delete, and replace.

With this basic DP approach in hand, let’s continue applying the “four-step problem-solving framework” to produce a complete solution.

Applying the Four-Step Framework

As usual, we use the four-step DP problem-solving framework to write the solution code.

Step 1: Define the Subproblem

As discussed above, we’ve identified the subproblem pattern for two-string DP problems. Similar to the Longest Common Subsequence (LCS) problem, we define subproblem $f(i, j)$ as “the edit distance between s[0..i) and t[0..j).” This makes it a two-dimensional DP problem.

Step 2: Write the Recurrence Relation

The recurrence relation corresponds to the three edit operations. For the edit distance between s[0..i) and t[0..j), we have three options:

Delete s[i-1], then compute the edit distance between s[0..i-1) and t[0..j)
Insert t[j-1], then compute the edit distance between s[0..i) and t[0..j-1)
Replace s[i-1] with t[j-1], then compute the edit distance between s[0..i-1) and t[0..j-1)

Among these three options, we need to find the one with the fewest operations. Written as a formula:

f(i, j) = \min \begin{cases} f(i-1, j) + 1\\ f(i, j-1) + 1\\ f(i-1, j-1) + 1 \end{cases}

Note that for the “replace” option above, if s[i-1] and t[j-1] are already equal, no replacement is needed, saving one edit operation. So we need to compare the last characters of s[0..i) and t[0..j), namely s[i-1] and t[j-1]. There are two possible cases:

Case 1: If s[i-1] != t[j-1], we can perform “insert,” “delete,” or “replace.”

Case 2: If s[i-1] == t[j-1], the last characters require no editing. We can strip them off and compute the edit distance between s[0..i-1) and t[0..j-1). Written as a formula:

f(i, j) = f(i-1, j-1)

Thus, the final recurrence relation is:

f(i, j) = \begin{cases} f(i-1, j-1), & \text{if } s_{i-1} = t_{j-1} \\ 1 + \min \begin{cases} f(i-1, j) \\ f(i, j-1) \\ f(i-1, j-1) \\ \end{cases}, & \text{if } s_{i-1} \ne t_{j-1} \\ \end{cases}

Also, don’t forget the base cases for the recurrence.

When $i = 0$ , s[0..i) is empty, with $j$ characters remaining in t[0..j). We need $j$ insert operations, so $f(0, j) = j$ .
When $j = 0$ , similarly, $f(i, 0) = i$ .

Step 3: Determine the Computation Order of the DP Array

For a 2D DP problem, we need to define a two-dimensional DP array where dp[i][j] corresponds to subproblem $f(i, j)$ , the edit distance between s[0..i) and t[0..j).

Let $m$ be the length of s and $n$ be the length of t. The ranges of $i$ and $j$ are: $0 \le i \le m, \; 0 \le j \le n$ . The DP array is an $m \times n$ rectangle.

To determine the computation order of the DP array, we need to know the dependency direction of the subproblems. Observing the recurrence relation, $f(i, j)$ depends on $f(i-1, j)$ , $f(i, j-1)$ , and $f(i-1, j-1)$ . We draw dependency arrows in the DP array:

Subproblem dependency directions in the DP array

We find that the subproblem dependency directions for the edit distance problem are exactly the same as for the LCS problem! This is because in both problems, $f(i, j)$ depends on $f(i-1, j)$ , $f(i, j-1)$ , and $f(i-1, j-1)$ . Although the specific recurrence relations differ, as long as the dependency structure is the same, the computation order of the DP array is identical.

Therefore, for the edit distance problem, the DP array is computed left-to-right, top-to-bottom. We should iterate through the DP array in this order:

for (int i = 0; i <= m; i++) {
    for (int j = 0; j <= n; j++) {
        // compute dp[i][j] ...
    }
}

The final solution code is:

public int minDistance(String s, String t) {
    // Subproblem:
    // f(i, j) = edit distance between s[0..i) and t[0..j)

    // f(0, j) = j
    // f(i, 0) = i
    // f(i, j) = f(i-1, j-1), if s[i-1] == t[j-1]
    //           max: f(i-1, j) + 1
    //                f(i, j-1) + 1
    //                f(i-1, j-1) + 1, if s[i-1] != t[j-1]

    int m = s.length();
    int n = t.length();
    int[][] dp = new int[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0) {
                dp[i][j] = j;
            } else if (j == 0) {
                dp[i][j] = i;
            } else {
                if (s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = 1 + min3(
                        dp[i-1][j],  // delete
                        dp[i][j-1],  // insert
                        dp[i-1][j-1] // replace
                    );
                }
            }
        }
    }
    return dp[m][n];
}

private int min3(int x, int y, int z) {
    return Math.min(x, Math.min(y, z));
}

The time and space complexity of this algorithm are both $O(mn)$ , where $m$ and $n$ represent the lengths of s and t, respectively.

Step 4: Space Optimization (Optional)

The edit distance problem is already a fairly difficult problem, so writing the basic solution is sufficient. In interviews, you generally won’t be asked about space optimization.

In fact, edit distance, LCS, and similar problems share a common space optimization technique. I’ll write a dedicated article later to cover various space optimization patterns for dynamic programming.

Drawing Inspiration from the LCS Problem

Above, we explained how to break down subproblems when you already know the problem uses dynamic programming. But you might ask: when you first encounter this problem, how can you tell it’s a DP problem?

The answer is simple: draw connections from problems you’ve solved before. If a problem reminds you of a DP problem you’ve seen, it can most likely be solved with dynamic programming.

The edit distance problem is actually very similar to the Longest Common Subsequence (LCS) problem we discussed previously. Both are “two-string” problems that involve comparing two strings. The connection is easy to make.

If you’re not familiar with the LCS problem, you can review the previous article:

LeetCode Example Walkthrough | 15 Longest Common Subsequence: 2D Dynamic Programming Solution

I chose LCS as the introductory example for 2D dynamic programming precisely because its approach is so classic that many other problems bear its imprint.

The LCS problem actually contains two useful problem-solving patterns:

Generally, problems involving “subsequences” are solved using dynamic programming.
Generally, DP problems involving two strings can use two pointers i and j pointing to the ends of the two strings, moving backward. That is, we define subproblem $f(i, j)$ to represent the substrings s[0..i) and t[0..j).

The LCS problem is about finding a common subsequence. At first glance, the edit distance problem doesn’t seem to involve subsequences, but when you think about it, the two are remarkably similar.

Look closely at the three operations in the edit distance problem: “insert,” “delete,” and “replace.” Among these, “insert” and “delete” are inverse operations. Characters inserted when converting s to t are equivalent to characters deleted when converting t to s.

We can actually reclassify and reorder all operations into three phases:

First, perform “delete” operations to convert s into a subsequence s' of s;
Next, perform “replace” operations to convert s' into a subsequence t' of t;
Finally, perform “insert” operations to convert t' into t.

For example, the figure below shows an actual conversion from “intention” to “execution”:

Reclassifying and reordering insert, delete, and replace operations

This shows that the edit distance problem is also very similar to “subsequence” problems. So it’s quite natural to think of a dynamic programming solution from this perspective.

Once we realize that DP applies, we can break down the subproblems based on the specific problem description, as we’ve already explained in the earlier sections.

Summary

This article used the edit distance problem to demonstrate techniques for analyzing DP approaches in real problems. Many difficult DP problems require certain decomposition skills. For example, two well-known ones:

(Both problems are quite challenging; beginners should not attempt them lightly.)

Additionally, this article highlighted the similarities between the edit distance problem and LCS. Because the subproblem dependency structures are the same in both problems, the computation order of the DP array is also identical. In fact, many DP problems can be understood by analogy. When practicing, thoroughly understanding the problems you’ve solved will give you more ideas when tackling new ones.