Classic DP: Edit Distance

A few days ago, I reviewed an interview question from Tencent. Most of the algorithm section was about dynamic programming, and the last question was to write a function to calculate the edit distance. Today, I'll dedicate an article to exploring this problem.

LeetCode Problem 72, "Edit Distance," is exactly this issue. Let's look at the question first:

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

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

// The function signature is as follows
int minDistance(String s1, String s2)

// The function signature is as follows
int minDistance(string s1, string s2)

# The function signature is as follows
def minDistance(s1: str, s2: str) -> int:

// the function signature is as follows
func minDistance(s1 string, s2 string) int {}

// The function signature is as follows
var minDistance = function(s1, s2) {}

For readers who are new to dynamic programming problems, this question might seem quite challenging. Do you feel completely lost on where to start?

However, this problem is quite practical. I've actually used this algorithm in real life. Previously, I made a mistake in a public account article and wrote a section incorrectly. I decided to revise this part to make the logic coherent. But the article could only be modified up to 20 characters, and only insertion, deletion, and replacement operations were allowed (just like the edit distance problem). So, I used an algorithm to find the optimal solution and completed the modification in just 16 steps.

For a more sophisticated application, consider DNA sequences, which are composed of A, G, C, T. These can be analogous to strings. Edit distance can measure the similarity between two DNA sequences. The smaller the edit distance, the more similar the two DNA sequences are, suggesting that their owners might be ancient relatives or something.

Now, let's get back to the topic and explain in detail how to calculate the edit distance. I believe this article will be beneficial for you.

1. Approach

The edit distance problem involves transforming one string s1 into another string s2 using three types of operations, and finding the minimum number of such operations. It's important to note that transforming s1 to s2 is equivalent to transforming s2 to s1, so we will use the former as an example.

Suppose the two strings are "rad" and "apple", and the pointers i and j point to the tails of s1 and s2, respectively. To transform s1 into s2, the algorithm proceeds as follows:

Remember this GIF process, as it will help you calculate the edit distance. The key is to perform the correct operations, which will be explained shortly.

From the GIF above, you can see that there is actually a fourth operation: do nothing (skip). For example, in this situation:

Since these two characters are already the same, to minimize the edit distance, obviously no operation should be performed. Simply move i and j forward.

Another easy-to-handle situation is when j reaches the end of s2 but i has not reached the end of s1. In this case, you can only use the delete operation to shorten s1 to match s2. For example:

Similarly, if i reaches the end of s1 while j has not reached the end of s2, you can only use the insert operation to add all the remaining characters of s2 to s1. These two situations are the base cases of the algorithm.

Next, let's detail how to translate this approach into code.

II. Code Explanation

Let's review the previous thought process:

The base case is when i reaches the end of s1 or j reaches the end of s2. You can directly return the remaining length of the other string.

For each pair of characters s1[i] and s2[j], there are four possible operations:

if s1[i] == s2[j]:
    Do nothing (skip)
    Move both `i` and `j` forward
else:
    Choose one of the three:
        Insert
        Delete
        Replace

With this framework, the problem is essentially solved. Readers might wonder, how do you decide among the "three choices"? It's simple: try all options, and choose the one that results in the smallest edit distance. This requires recursion. Let's first look at the brute-force solution code:

class Solution {
    public int minDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        // i, j are initialized to point to the last index
        return dp(s1, m - 1, s2, n - 1);
    }

    // definition: return the minimum edit distance between s1[0..i] and s2[0..j]
    int dp(String s1, int i, String s2, int j) {
        // base case
        if (i == -1) return j + 1;
        if (j == -1) return i + 1;

        if (s1.charAt(i) == s2.charAt(j)) {
            // do nothing
            return dp(s1, i - 1, s2, j - 1);
        }
        return min(
            // insert
            dp(s1, i, s2, j - 1) + 1,
            // delete
            dp(s1, i - 1, s2, j) + 1,
            // replace
            dp(s1, i - 1, s2, j - 1) + 1
        );
    }

    int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

class Solution {
public:
    int minDistance(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        // initialize i and j to point to the last index
        return dp(s1, m - 1, s2, n - 1);
    }

private:
    // definition: return the minimum edit distance between s1[0..i] and s2[0..j]
    int dp(string &s1, int i, string &s2, int j) {
        // base case
        if (i == -1) return j + 1;
        if (j == -1) return i + 1;

        if (s1[i] == s2[j]) {
            // do nothing
            return dp(s1, i - 1, s2, j - 1);
        }
        return min({
            // insert
            dp(s1, i, s2, j - 1) + 1,
            // delete
            dp(s1, i - 1, s2, j) + 1,
            // replace
            dp(s1, i - 1, s2, j - 1) + 1
        });
    }
};

class Solution:
    def minDistance(self, s1: str, s2: str) -> int:
        m = len(s1)
        n = len(s2)
        # initialize i and j to point to the last index
        return self.dp(s1, m - 1, s2, n - 1)

    # definition: return the minimum edit distance between s1[0..i] and s2[0..j]
    def dp(self, s1: str, i: int, s2: str, j: int) -> int:
        # base case
        if i == -1:
            return j + 1
        if j == -1:
            return i + 1

        if s1[i] == s2[j]:
            # do nothing
            return self.dp(s1, i - 1, s2, j - 1)

        return min(
            # insert
            self.dp(s1, i, s2, j - 1) + 1,
            # delete
            self.dp(s1, i - 1, s2, j) + 1,
            # replace
            self.dp(s1, i - 1, s2, j - 1) + 1
        )

func minDistance(s1 string, s2 string) int {
    m, n := len(s1), len(s2)
    // initialize i and j to point to the last index
    return dp(s1, m - 1, s2, n - 1)
}

// definition: return the minimum edit distance between s1[0..i] and s2[0..j]
func dp(s1 string, i int, s2 string, j int) int {
    // base case
    if i == -1 {
        return j + 1
    }
    if j == -1 {
        return i + 1
    }

    if s1[i] == s2[j] {
        // do nothing
        return dp(s1, i - 1, s2, j - 1)
    }
    return min(
        // insert
        dp(s1, i, s2, j - 1) + 1,
        // delete
        dp(s1, i - 1, s2, j) + 1,
        // replace
        dp(s1, i - 1, s2, j - 1) + 1
    )
}

var minDistance = function(s1, s2) {
    let m = s1.length, n = s2.length;
    // initialize i and j to point to the last index
    return dp(s1, m - 1, s2, n - 1);
}

// definition: return the minimum edit distance between s1[0..i] and s2[0..j]
var dp = function(s1, i, s2, j) {
    // base case
    if (i == -1) return j + 1;
    if (j == -1) return i + 1;

    if (s1.charAt(i) == s2.charAt(j)) {
        // do nothing
        return dp(s1, i - 1, s2, j - 1);
    }
    return min(
        // insert
        dp(s1, i, s2, j - 1) + 1,
        // delete
        dp(s1, i - 1, s2, j) + 1,
        // replace
        dp(s1, i - 1, s2, j - 1) + 1,
    );
}

var min = function(a, b, c) {
    return Math.min(a, Math.min(b, c));
}

Let's explain this recursive code in detail. The base case should be self-explanatory, so we'll focus on the recursive part.

It's often said that recursive code is easy to understand, and this is true. As long as you understand the function's definition, you can clearly grasp the logic of the algorithm. Here, the definition of our dp function is as follows:

// Definition: return the minimum edit distance between s1[0..i] and s2[0..j]
int dp(String s1, int i, String s2, int j)

// Definition: return the minimum edit distance between s1[0..i] and s2[0..j]
int dp(string s1, int i, string s2, int j)

# Definition: Return the minimum edit distance between s1[0..i] and s2[0..j]
def dp(s1: str, i: int, s2: str, j: int):

// Definition: return the minimum edit distance between s1[0..i] and s2[0..j]
func dp(s1 string, i int, s2 string, j int) int

// Definition: return the minimum edit distance between s1[0..i] and s2[0..j]
var dp = function(s1, i, s2, j)

记住这个定义之后，先来看这段代码：

if s1[i] == s2[j]:
    # do nothing
    return dp(s1, i - 1, s2, j - 1)
# explanation:
# they are already equal, no operation is needed
# the minimum edit distance between s1[0..i] and s2[0..j] is equal to
# the minimum edit distance between s1[0..i-1] and s2[0..j-1]
# that is, dp(i, j) is equal to dp(i-1, j-1)

如果 s1[i] != s2[j]，就要对三个操作递归了，稍微需要点思考：

# Insert
dp(s1, i, s2, j - 1) + 1,
# Explanation:
# I directly insert a character identical to s2[j] at s1[i]
# Then s2[j] is matched, move j forward, and continue to compare with i
# Don't forget to add one to the operation count

# delete
dp(s1, i - 1, s2, j) + 1,
# explanation:
# I directly delete the character s[i]
# move i forward and continue to compare with j
# increment the operation count

# Replace
dp(s1, i - 1, s2, j - 1) + 1
# Explanation:
# I directly replace s1[i] with s2[j], so they match
# Meanwhile, move i and j forward to continue the comparison
# Increment the operation count by one

Now, you should fully understand this concise code. However, there's a small issue: this solution is a brute-force approach and has overlapping subproblems, which need to be optimized using dynamic programming techniques.

How can we quickly identify overlapping subproblems? I've discussed this in the Dynamic Programming Q&A. Here, I'll briefly mention that you need to abstract the recursive framework of the algorithm:

int dp(int i, int j) {
    dp(i - 1, j - 1); // #1
    dp(i, j - 1);     // #2
    dp(i - 1, j);     // #3
}

For the subproblem dp(i-1, j-1), how can we derive it from the original problem dp(i, j)? There is more than one path, such as dp(i, j) -> #1 and dp(i, j) -> #2 -> #3. Once you find a repeated path, it indicates the presence of a large number of redundant paths, which is the overlapping subproblems issue.

3. Dynamic Programming Optimization

For overlapping subproblems, the previous article Detailed Explanation of Dynamic Programming provides a detailed introduction. The optimization methods involve either adding a memo to the recursive solution or implementing the dynamic programming process using a DP table iteratively. Let's discuss these methods one by one.

Memoization Solution

Since the brute-force recursive solution is already written, adding a memo is quite easy with minor modifications to the original code:

class Solution {
    // memoization
    int[][] memo;
        
    public int minDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        // initialize the memoization with a
        // special value, indicating it has not been
        memo = new int[m][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return dp(s1, m - 1, s2, n - 1);
    }

    int dp(String s1, int i, String s2, int j) {
        if (i == -1) return j + 1;
        if (j == -1) return i + 1;
        // check the memoization to avoid overlapping subproblems
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // state transition, store the result in memoization
        if (s1.charAt(i) == s2.charAt(j)) {
            memo[i][j] = dp(s1, i - 1, s2, j - 1);
        } else {
            memo[i][j] =  min(
                dp(s1, i, s2, j - 1) + 1,
                dp(s1, i - 1, s2, j) + 1,
                dp(s1, i - 1, s2, j - 1) + 1
            );
        }
        return memo[i][j];
    }

    int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

class Solution {
private:
    // memoization table
    vector<vector<int>> memo;
    int dp(string& s1, int i, string& s2, int j) {
        if (i == -1) return j + 1;
        if (j == -1) return i + 1;
        // check memoization table to avoid overlapping subproblems
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // state transition, store the result in the memoization table
        if (s1[i] == s2[j]) {
            memo[i][j] = dp(s1, i - 1, s2, j - 1);
        } else {
            memo[i][j] = min3(
                dp(s1, i, s2, j - 1) + 1,
                dp(s1, i - 1, s2, j) + 1,
                dp(s1, i - 1, s2, j - 1) + 1
            );
        }
        return memo[i][j];
    }

    int min3(int a, int b, int c) {
        return min(a, min(b, c));
    }

public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        // initialize the memoization table with a
        // special value, indicating it has not been
        memo = vector<vector<int>>(m, vector<int>(n, -1));
        return dp(word1, m - 1, word2, n - 1);
    }
};

class Solution:
    def __init__(self):
        self.memo = []

    def minDistance(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        # Initialize the memoization table with a special
        # value, indicating that it has not been
        self.memo = [[-1] * n for _ in range(m)]
        return self.dp(s1, m - 1, s2, n - 1)

    def dp(self, s1: str, i: int, s2: str, j: int) -> int:
        if i == -1:
            return j + 1
        if j == -1:
            return i + 1

        # Check the memoization table to avoid overlapping subproblems
        if self.memo[i][j] != -1:
            return self.memo[i][j]

        # State transition, store the result in the memoization table
        if s1[i] == s2[j]:
            self.memo[i][j] = self.dp(s1, i - 1, s2, j - 1)
        else:
            self.memo[i][j] = min(
                self.dp(s1, i, s2, j - 1) + 1,
                self.dp(s1, i - 1, s2, j) + 1,
                self.dp(s1, i - 1, s2, j - 1) + 1
            )

        return self.memo[i][j]

func minDistance(s1 string, s2 string) int {
    // memoization table
    memo := make([][]int, len(s1))
    for i := range memo {
        memo[i] = make([]int, len(s2))
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    return dp(s1, len(s1)-1, s2, len(s2)-1, memo)
}

func dp(s1 string, i int, s2 string, j int, memo [][]int) int {
    if i == -1 {
        return j + 1
    }
    if j == -1 {
        return i + 1
    }
    // check the memoization table to avoid overlapping subproblems
    if memo[i][j] != -1 {
        return memo[i][j]
    }
    // state transition, store the result in the memoization table
    if s1[i] == s2[j] {
        memo[i][j] = dp(s1, i-1, s2, j-1, memo)
    } else {
        memo[i][j] = min(
            dp(s1, i, s2, j-1, memo)+1,
            dp(s1, i-1, s2, j, memo)+1,
            dp(s1, i-1, s2, j-1, memo)+1,
        )
    }
    return memo[i][j]
}

func min(a int, b int, c int) int {
    if a < b {
        if a < c {
            return a
        }
        return c
    }
    if b < c {
        return b
    }
    return c
}

var minDistance = function(s1, s2) {
    let memo = [];
    let m = s1.length, n = s2.length;
    // Initialize the memoization array with a special
    // value, indicating that it has not been calculated
    for (let i = 0; i <= m; i++) {
        memo[i] = new Array(n + 1).fill(-1);
    }
    return dp(s1, m - 1, s2, n - 1, memo);
};

function dp(s1, i, s2, j, memo) {
    if (i == -1) return j + 1;
    if (j == -1) return i + 1;
    // Check the memoization array to avoid overlapping subproblems
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    // State transition, store the result in the memoization array
    if (s1.charAt(i) == s2.charAt(j)) {
        memo[i][j] = dp(s1, i - 1, s2, j - 1, memo);
    } else {
        memo[i][j] = Math.min(
            dp(s1, i, s2, j - 1, memo) + 1,
            dp(s1, i - 1, s2, j, memo) + 1,
            dp(s1, i - 1, s2, j - 1, memo) + 1
        );
    }
    return memo[i][j];
}

DP Table Solution

Let's focus on the DP table solution. We need to define a dp array and then perform state transitions on this array.

First, clarify the meaning of the dp array. Since this problem has two states (indexes i and j), the dp array is a two-dimensional array, looking something like this:

The state transition is the same as the recursive solution. dp[..][0] and dp[0][..] correspond to the base cases, and the meaning of dp[i][j] is similar to the previous definition of the dp function:

int dp(String s1, int i, String s2, int j)
// return the minimum edit distance between s1[0..i] and s2[0..j]

dp[i-1][j-1]
// store the minimum edit distance between s1[0..i] and s2[0..j]

The base case for the dp function is when i and j are equal to -1, while array indices start at 0, so the dp array will be offset by one position.

Since the dp array and the recursive dp function have the same meaning, you can directly apply the previous approach to write the code. The only difference is that the recursive solution is solved top-down (starting from the original problem and gradually breaking it down to the base case), whereas the DP table is solved bottom-up (starting from the base case and working up to the original problem):

class Solution {
    public int minDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        // definition: the minimum edit distance between s1[0..i] and s2[0..j] is dp[i+1][j+1]
        int[][] dp = new int[m + 1][n + 1];
        // base case 
        for (int i = 1; i <= m; i++)
            dp[i][0] = i;
        for (int j = 1; j <= n; j++)
            dp[0][j] = j;
        // Solve from bottom to top
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(
                        dp[i - 1][j] + 1,

                        dp[i][j - 1] + 1,

                        dp[i - 1][j - 1] + 1

                    );
                }
            }
        }
        // Stores the minimum edit distance between the entire s1 and s2
        return dp[m][n];
    }

    int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

class Solution {
public:
    int minDistance(string s1, string s2) {
        int m = s1.length(), n = s2.length();
        // Definition: the minimum edit distance between s1[0..i] and s2[0..j] is dp[i+1][j+1]
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        // base case 
        for (int i = 1; i <= m; i++)
            dp[i][0] = i;
        for (int j = 1; j <= n; j++)
            dp[0][j] = j;
        // Solve from bottom to top
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i-1] == s2[j-1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min3(
                        dp[i - 1][j] + 1,

                        dp[i][j - 1] + 1,

                        dp[i - 1][j - 1] + 1

                    );
                }
            }
        }
        // Stores the minimum edit distance between the entire s1 and s2
        return dp[m][n];
    }

    int min3(int a, int b, int c) {
        return std::min(a, std::min(b, c));
    }
};

class Solution:
    def minDistance(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        # definition: the minimum edit distance between s1[0..i] and s2[0..j] is dp[i+1][j+1]
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        # base case 
        for i in range(1, m + 1):
            dp[i][0] = i
        for j in range(1, n + 1):
            dp[0][j] = j
        # Solve from bottom to top
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(
                        dp[i - 1][j] + 1, 

                        dp[i][j - 1] + 1, 

                        dp[i - 1][j - 1] + 1

                    )
        # Stores the minimum edit distance between the entire s1 and s2
        return dp[m][n]

func minDistance(s1 string, s2 string) int {
    m, n := len(s1), len(s2)
    // Definition: the minimum edit distance between s1[0..i] and s2[0..j] is dp[i+1][j+1]
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    // base case
    for i := 1; i <= m; i++ {
        dp[i][0] = i
    }
    for j := 1; j <= n; j++ {
        dp[0][j] = j
    }
    // Solve from bottom to top
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(
                    dp[i-1][j]+1,

                    dp[i][j-1]+1,

                    dp[i-1][j-1]+1,

                )
            }
        }
    }
    // Stores the minimum edit distance between the entire s1 and s2
    return dp[m][n]
}

func min(args ...int) int {
    minVal := args[0]
    for _, val := range args {
        if val < minVal {
            minVal = val
        }
    }
    return minVal
}

var minDistance = function(s1, s2) {
    var m = s1.length, n = s2.length;
    // definition: the minimum edit distance between s1[0..i] and s2[0..j] is dp[i+1][j+1]
    var dp = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
    // base case 
    for (var i = 1; i <= m; i++)
        dp[i][0] = i;
    for (var j = 1; j <= n; j++)
        dp[0][j] = j;
    // Solve from bottom to top
    for (var i = 1; i <= m; i++) {
        for (var j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    dp[i - 1][j] + 1,
                    /*<extend up -300>
                    <div class="img-content"><img src="/images/editDistance/delete.gif" alt class="myimage" loading="lazy" photo-swipe="" /></div>
                    */
                    dp[i][j - 1] + 1,
                    /*<extend up -300>
                    <div class="img-content"><img src="/images/editDistance/insert.gif" alt class="myimage" loading="lazy" photo-swipe="" /></div>
                    */
                    dp[i - 1][j - 1] + 1
                    /*<extend up -300>
                    <div class="img-content"><img src="/images/editDistance/replace.gif" alt class="myimage" loading="lazy" photo-swipe="" /></div>
                    */
                );
            }
        }
    }
    // Stores the minimum edit distance between the entire s1 and s2
    return dp[m][n];
};

4. Further Exploration

Generally, when dealing with dynamic programming problems involving two strings, the approach discussed in this article is used to create a DP table. Why is this approach taken? Because it makes it easier to identify the relationship of state transitions, such as the DP table for edit distance:

There is also a detail to note: since each dp[i][j] is only related to the three adjacent states, the space complexity can be reduced to $O(min(M, N))$, where M and N are the lengths of the two strings. This optimization is not difficult but reduces the clarity significantly. Readers are encouraged to try optimizing it themselves.

You might also ask, here we only find the minimum edit distance, but what are the specific operations? In the example of modifying a public account article mentioned earlier, knowing just the minimum edit distance is not enough; you also need to know how to make the specific changes.

This is actually quite simple. By slightly modifying the code and adding extra information to the dp array, you can achieve this:

// int[][] dp;
Node[][] dp;

class Node {
    int val;
    int choice;
    // 0 represents doing nothing
    // 1 represents insertion
    // 2 represents deletion
    // 3 represents replacement
}

class Node {
public:
    int val;
    int choice;
    // 0 represents doing nothing
    // 1 represents insertion
    // 2 represents deletion
    // 3 represents replacement
};

vector<vector<Node>> dp;

class Node:
    val: int
    choice: int
    # 0 represents doing nothing
    # 1 represents insertion
    # 2 represents deletion
    # 3 represents replacement

dp: List[List[Node]] = []

// Node struct
type Node struct {
    val    int
    choice int
    // 0 means do nothing
    // 1 means insert
    // 2 means delete
    // 3 means replace
}

var dp [][]Node

function Node() {
    this.val = 0;
    this.choice = 0;
    // 0 represents doing nothing
    // 1 represents insertion
    // 2 represents deletion
    // 3 represents replacement
}

The val attribute represents the value from the previous dp array, and the choice attribute represents the operation. When making the optimal choice, we also record the operation, allowing us to backtrack the specific operations from the result.

Our final result is dp[m][n], right? Here, val stores the minimum edit distance, and choice stores the last operation. For example, if the last operation was an insertion, we can move one step to the left:

By repeating this process, we can step back to the starting point dp[0][0], forming a path. Following the operations on this path gives us the optimal solution.

As requested by many, I've written out this approach. You can run it yourself to try it out:

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    Node[][] dp = new Node[m + 1][n + 1];
    // base case
    for (int i = 0; i <= m; i++) {
        // transforming s1 to s2 only requires deleting a character
        dp[i][0] = new Node(i, 2);
    }
    for (int j = 1; j <= n; j++) {
        // transforming s1 to s2 only requires inserting a character
        dp[0][j] = new Node(j, 1);
    }
    // state transition equation
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)){
                // if the two characters are the same, nothing needs to be done
                Node node = dp[i - 1][j - 1];
                dp[i][j] = new Node(node.val, 0);
            } else {
                // otherwise, record the operation with the minimum cost
                dp[i][j] = minNode(
                    dp[i - 1][j],
                    dp[i][j - 1],
                    dp[i-1][j-1]
                );
                // and increment the edit distance by one
                dp[i][j].val++;
            }
        }
    }
    // deduce the specific operation process based on the dp table and print it
    printResult(dp, s1, s2);
    return dp[m][n].val;
}

// calculate the operation with the minimum cost among delete, insert, replace
Node minNode(Node a, Node b, Node c) {
    Node res = new Node(a.val, 2);
    
    if (res.val > b.val) {
        res.val = b.val;
        res.choice = 1;
    }
    if (res.val > c.val) {
        res.val = c.val;
        res.choice = 3;
    }
    return res;
}

int minDistance(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<Node>> dp(m + 1, vector<Node>(n + 1));
    // base case
    for (int i = 0; i <= m; i++) {
        // converting s1 to s2 requires only deleting one character
        dp[i][0] = Node{i, 2};
    }
    for (int j = 1; j <= n; j++) {
        // converting s1 to s2 requires only inserting one character
        dp[0][j] = Node{j, 1};
    }
    // state transition equation
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]){
                // if the two characters are the same, nothing needs to be done
                Node node = dp[i - 1][j - 1];
                dp[i][j] = Node{node.val, 0};
            } else {
                // otherwise, record the operation with the minimum cost
                dp[i][j] = minNode(
                    dp[i - 1][j],
                    dp[i][j - 1],
                    dp[i-1][j-1]
                );
                // and increment the edit distance by one
                dp[i][j].val++;
            }
        }
    }
    // deduce the specific operation process based on the dp table and print it
    printResult(dp, s1, s2);
    return dp[m][n].val;
}

// calculate the operation with the minimum cost among delete, insert, replace
Node minNode(Node a, Node b, Node c) {
    Node res = a;
    if (res.val > b.val) {
        res = b;
    }
    if (res.val > c.val) {
        res = c;
    }
    return res;
}

def minDistance(self, s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[Node() for _ in range(n + 1)] for _ in range(m + 1)]
    # base case
    for i in range(m + 1):
        # converting s1 to s2 requires only deleting one character
        dp[i][0] = Node(i, 2)
    for j in range(1, n + 1):
        # converting s1 to s2 requires only inserting one character
        dp[0][j] = Node(j, 1)
    # state transition equation
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                # if the two characters are the same, nothing needs to be done
                node = dp[i - 1][j - 1]
                dp[i][j] = Node(node.val, 0)
            else:
                # otherwise, record the operation with the minimum cost
                dp[i][j] = self.minNode(
                    dp[i - 1][j],
                    dp[i][j - 1],
                    dp[i-1][j-1]
                )
                # and increment the edit distance by one
                dp[i][j].val += 1
    # deduce the specific operation process based on the dp table and print it
    self.printResult(dp, s1, s2)
    return dp[m][n].val

# calculate the operation with the minimum cost among delete, insert, replace
def minNode(self, a: Node, b: Node, c: Node) -> Node:
    res = a
    if res.val > b.val:
        res = b
    if res.val > c.val:
        res = c
    return res

func minDistance(s1 string, s2 string) int {
    m, n := len(s1), len(s2)
    dp := make([][]Node, m+1)
    for i := range dp {
        dp[i] = make([]Node, n+1)
    }
    // base case
    for i := 0; i <= m; i++ {
        // converting s1 to s2 requires only deleting one character
        dp[i][0] = Node{val: i, choice: 2}
    }
    for j := 1; j <= n; j++ {
        // converting s1 to s2 requires only inserting one character
        dp[0][j] = Node{val: j, choice: 1}
    }
    // state transition equation
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                // if the two characters are the same, nothing needs to be done
                node := dp[i-1][j-1]
                dp[i][j] = Node{val: node.val, choice: 0}
            } else {
                // otherwise, record the operation with the smallest cost
                dp[i][j] = minNode(
                    dp[i-1][j],
                    dp[i][j-1],
                    dp[i-1][j-1],
                )
                // and increment the edit distance by one
                dp[i][j].val++
            }
        }
    }
    // deduce the specific operation process based on the dp table and print it
    printResult(dp, s1, s2)
    return dp[m][n].val
}

// calculate the operation with the smallest cost among delete, insert, replace
func minNode(a, b, c Node) Node {
    res := a
    if res.val > b.val {
        res = b
    }
    if res.val > c.val {
        res = c
    }
    return res
}

function minDistance(s1, s2) {
    var m = s1.length, n = s2.length;
    var dp = Array.from({length: m + 1}, () => Array(n + 1).fill(new Node()));
    // base case
    for (var i = 0; i <= m; i++) {
        // converting s1 to s2 requires only deleting one character
        dp[i][0] = new Node(i, 2);
    }
    for (var j = 1; j <= n; j++) {
        // converting s1 to s2 requires only inserting one character
        dp[0][j] = new Node(j, 1);
    }
    // state transition equation
    for (var i = 1; i <= m; i++) {
        for (var j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                // if two characters are the same, nothing needs to be done
                var node = dp[i - 1][j - 1];
                dp[i][j] = new Node(node.val, 0);
            } else {
                // otherwise, record the operation with the minimum cost
                dp[i][j] = minNode(
                    dp[i - 1][j],
                    dp[i][j - 1],
                    dp[i-1][j-1]
                );
                // and increment the edit distance by one
                dp[i][j].val++;
            }
        }
    }
    // deduce the specific operation process based on the dp table and print it
    printResult(dp, s1, s2);
    return dp[m][n].val;
}

// calculate the operation with the minimum cost among delete, insert, replace
function minNode(a, b, c) {
    var res = a;
    if (res.val > b.val) {
        res = b;
    }
    if (res.val > c.val) {
        res = c;
    }
    return res;
}

最后，printResult 函数反推结果并把具体的操作打印出来：

void printResult(Node[][] dp, String s1, String s2) {
    int rows = dp.length;
    int cols = dp[0].length;
    int i = rows - 1, j = cols - 1;
    System.out.println("Change s1=" + s1 + " to s2=" + s2 + ":\n");
    while (i != 0 && j != 0) {
        char c1 = s1.charAt(i - 1);
        char c2 = s2.charAt(j - 1);
        int choice = dp[i][j].choice;
        System.out.print("s1[" + (i - 1) + "]:");
        switch (choice) {
            case 0:
                // skip, then both pointers move forward
                System.out.println("skip '" + c1 + "'");
                i--; j--;
                break;
            case 1:
                // insert s2[j] into s1[i], then the s2 pointer moves forward
                System.out.println("insert '" + c2 + "'");
                j--;
                break;
            case 2:
                // delete s1[i], then the s1 pointer moves forward
                System.out.println("delete '" + c1 + "'");
                i--;
                break;
            case 3:
                // replace s1[i] with s2[j], then both pointers move forward
                System.out.println(
                    "replace '" + c1 + "'" + " with '" + c2 + "'");
                i--; j--;
                break;
        }
    }
    // if s1 is not finished, the remaining characters need to be deleted
    while (i > 0) {
        System.out.print("s1[" + (i - 1) + "]:");
        System.out.println("delete '" + s1.charAt(i - 1) + "'");
        i--;
    }
    // if s2 is not finished, the remaining characters need to be inserted into s1
    while (j > 0) {
        System.out.print("s1[0]:");
        System.out.println("insert '" + s2.charAt(j - 1) + "'");
        j--;
    }
}

void printResult(vector<vector<Node>>& dp, string s1, string s2) {
    int rows = dp.size();
    int cols = dp[0].size();
    int i = rows - 1, j = cols - 1;
    cout << "Change s1=" << s1 << " to s2=" << s2 << ":\n" << endl;
    while (i != 0 && j != 0) {
        char c1 = s1[i - 1];
        char c2 = s2[j - 1];
        int choice = dp[i][j].choice;
        cout << "s1[" << i - 1 << "]:";
        switch (choice) {
            case 0:
                // skip, then both pointers move forward
                cout << "skip '" << c1 << "'" << endl;
                i--; j--;
                break;
            case 1:
                // insert s2[j] into s1[i], then the s2 pointer moves forward
                cout << "insert '" << c2 << "'" << endl;
                j--;
                break;
            case 2:
                // delete s1[i], then the s1 pointer moves forward
                cout << "delete '" << c1 << "'" << endl;
                i--;
                break;
            case 3:
                // replace s1[i] with s2[j], then both pointers move forward
                cout << "replace '" << c1 << "' with '" << c2 << "'" << endl;
                i--; j--;
                break;
        }
    }
    // if s1 is not finished, the remaining characters need to be deleted
    while (i > 0) {
        cout << "s1[" << i - 1 << "]:";
        cout << "delete '" << s1[i - 1] << "'" << endl;
        i--;
    }
    // if s2 is not finished, the remaining characters need to be inserted into s1
    while (j > 0) {
        cout << "s1[0]:";
        cout << "insert '" << s2[j - 1] << "'" << endl;
        j--;
    }
}

def printResult(self, dp, s1, s2):
    rows = len(dp)
    cols = len(dp[0])
    i, j = rows - 1, cols - 1
    print(f"Change s1={s1} to s2={s2}:\n")
    while i != 0 and j != 0:
        c1 = s1[i - 1]
        c2 = s2[j - 1]
        choice = dp[i][j].choice
        print(f"s1[{i - 1}]:", end='')
        if choice == 0:
            # skip, then both pointers move forward
            print(f"skip '{c1}'")
            i -= 1
            j -= 1
        elif choice == 1:
            # insert s2[j] into s1[i], then the s2 pointer moves forward
            print(f"insert '{c2}'")
            j -= 1
        elif choice == 2:
            # delete s1[i], then the s1 pointer moves forward
            print(f"delete '{c1}'")
            i -= 1
        elif choice == 3:
            # replace s1[i] with s2[j], then both pointers move forward
            print(f"replace '{c1}' with '{c2}'")
            i -= 1
            j -= 1
    # if s1 is not finished, the remaining characters need to be deleted
    while i > 0:
        print(f"s1[{i - 1}]:", end='')
        print(f"delete '{s1[i - 1]}'")
        i -= 1
    # if s2 is not finished, the remaining characters need to be inserted into s1
    while j > 0:
        print(f"s1[0]:", end='')
        print(f"insert '{s2[j - 1]}'")
        j -= 1

func printResult(dp [][]Node, s1, s2 string) {
    rows := len(dp)
    cols := len(dp[0])
    i, j := rows - 1, cols - 1
    fmt.Printf("Change s1=%s to s2=%s:\n\n", s1, s2)
    for i != 0 && j != 0 {
        c1 := s1[i-1]
        c2 := s2[j-1]
        choice := dp[i][j].choice
        fmt.Printf("s1[%d]:", i-1)
        switch choice {
        case 0:
            // skip, then both pointers move forward
            fmt.Printf("skip '%c'\n", c1)
            i--
            j--
        case 1:
            // insert s2[j] into s1[i], then the s2 pointer moves forward
            fmt.Printf("insert '%c'\n", c2)
            j--
        case 2:
            // delete s1[i], then the s1 pointer moves forward
            fmt.Printf("delete '%c'\n", c1)
            i--
        case 3:
            // replace s1[i] with s2[j], then both pointers move forward
            fmt.Printf("replace '%c' with '%c'\n", c1, c2)
            i--
            j--
        }
    }
    // if s1 is not finished, the remaining characters need to be deleted
    for i > 0 {
        fmt.Printf("s1[%d]:", i-1)
        fmt.Printf("delete '%c'\n", s1[i-1])
        i--
    }
    // if s2 is not finished, the remaining characters need to be inserted into s1
    for j > 0 {
        fmt.Printf("s1[0]:")
        fmt.Printf("insert '%c'\n", s2[j-1])
        j--
    }
}

function printResult(dp, s1, s2) {
    var rows = dp.length;
    var cols = dp[0].length;
    var i = rows - 1, j = cols - 1;
    console.log(`Change s1=${s1} to s2=${s2}:\n`);
    while (i != 0 && j != 0) {
        var c1 = s1[i - 1];
        var c2 = s2[j - 1];
        var choice = dp[i][j].choice;
        console.log(`s1[${i - 1}]:`, end='');
        switch (choice) {
            case 0:
                // skip, then both pointers move forward
                console.log(`skip '${c1}'`);
                i--;
                j--;
                break;
            case 1:
                // insert s2[j] into s1[i], then the s2 pointer moves forward
                console.log(`insert '${c2}'`);
                j--;
                break;
            case 2:
                // delete s1[i], then the s1 pointer moves forward
                console.log(`delete '${c1}'`);
                i--;
                break;
            case 3:
                // replace s1[i] with s2[j], then both pointers move forward
                console.log(`replace '${c1}' with '${c2}'`);
                i--;
                j--;
                break;
        }
    }
    // if s1 is not finished, the remaining characters need to be deleted
    while (i > 0) {
        console.log(`s1[${i - 1}]:`, end='');
        console.log(`delete '${s1[i - 1]}'`);
        i--;
    }
    // if s2 is not finished, the remaining characters need to be inserted into s1
    while (j > 0) {
        console.log(`s1[0]:`, end='');
        console.log(`insert '${s2[j - 1]}'`);
        j--;
    }
}