经典动态规划：编辑距离
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 72. Edit Distance | 🔴 |
Prerequisites
Before reading this article, you should learn:
Tip
本文有视频版：Detailed Explanation of Edit Distance using Dynamic Programming。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。
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:
72. Edit Distance | 力扣 | LeetCode |
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Example 1:
Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')
Example 2:
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')
Constraints:
0 <= word1.length, word2.length <= 500word1andword2consist of lowercase English letters.
// 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.
I. Approach
The edit distance problem gives us two strings s1 and s2, and allows only three operations to transform s1 into s2, asking for the minimum number of operations. It's important to note that whether transforming s1 into s2 or vice versa, the result is the same, so we will use s1 to s2 as an example in the following text.
In the previous article Longest Common Subsequence, it was mentioned that solving dynamic programming problems involving two strings generally involves using two pointers i and j pointing to the ends of the two strings, then moving step by step towards the beginning to reduce the problem's scale.
提示
Actually, moving i and j from the beginning to the end is also possible; you just need to adjust the definition of the dp function/array. The approach is exactly the same.
Consider two strings "rad" and "apple". To transform s1 into s2, the algorithm proceeds as follows:
Please remember this GIF process, as it helps in calculating the edit distance. The key is to make the correct operations, which will be discussed shortly.
From the GIF above, you can see that there are not just three operations, but actually a fourth one: doing nothing (skip). For example:
Since these two characters are already the same, to minimize the edit distance, it's obvious that no operation should be performed on them. Just move i and j forward.
Another easily handled situation is when j finishes traversing s2 but i hasn't finished s1. In this case, only deletion operations can be used to shorten s1 to match s2. For example:
Similarly, if i finishes s1 but j hasn't finished s2, then only insertion operations can be used to add the remaining characters of s2 to s1. These two situations are the base cases of the algorithm.
Next, let's delve into 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
ReplaceWith 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);
}
// define: 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 and efficient code. However, there's a small issue: this solution is a brute-force approach with overlapping subproblems, which needs to be optimized using dynamic programming techniques.
How can you quickly identify overlapping subproblems? Let's briefly revisit the recursive framework of the algorithm in this article:
int dp(i, 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 it be derived from the original problem dp(i, j)? There are multiple paths, such as dp(i, j) -> #1 and dp(i, j) -> #2 -> #3. Once you find a repeated path, it indicates the presence of a massive number of repeated paths, which are overlapping subproblems.
III. Dynamic Programming Optimization
Regarding overlapping subproblems, the previous article Dynamic Programming Detailed Explanation provided a detailed introduction. The optimization methods involve either adding a memoization to the recursive solution or iteratively implementing the dynamic programming process using a DP table. Let's discuss these methods one by one.
Memoization Solution
Since the brute-force recursive solution is already written, adding memoization is straightforward. You just need to make slight 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 calculated
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 calculated
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 calculated yet
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 yet
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();
// Define: 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)
# Define: 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;
// Define: 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];
};IV. Extensions and Further Insights
Generally, when dealing with dynamic programming problems involving two strings, the approach outlined in this article is followed, which involves setting up a DP table. Why? Because it makes it easier to identify the state transition relationships, such as in the DP table for edit distance:
There's also a detail to note: since each dp[i][j] only depends on its three neighboring states, the space complexity can be reduced to O(min(M, N)) (where M and N are the lengths of the two strings). While this optimization isn't difficult, it does reduce the code's readability. Readers are encouraged to try optimizing this themselves.
You might also wonder, "We've only calculated the minimum edit distance, but what about the specific operations?" For instance, in the example of modifying a public account article, knowing just the minimum edit distance isn't enough; you also need to know exactly how to make the modifications.
This is actually quite simple. By making slight modifications to 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 [][]Nodefunction 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 resfunc 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 -= 1func 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--;
}
}