引言
你有没有想过，拼写软件是如何知道你想输入哪个单词的？DNA序列比对又是如何衡量相似度的？这一切的背后，都离不开一个经典算法——编辑距离。它通过计算字符串之间最少的插入、删除和替换次数，来衡量两个文本的相似程度。本文将以 LeetCode 第 72 题为例，从零开始推导动态规划解法，并通过详细的代码注释带你一步步掌握这道题的完整思路。
目录
一、题目描述
二、动态规划思路
三、Java代码实现
四、运行结果
五、软考真题
一、题目描述
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：
- 0 <= word1.length, word2.length <= 500
- word1 和 word2 由小写英文字母组成
二、动态规划思路
这是一个典型的动态规划问题。我们可以把大问题分解成小问题：
定义状态：
-
设 dp[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数。
状态转移： 考虑 word1[i-1] 和 word2[j-1]（注意索引从0开始）：
1. 如果这两个字符相同，则不需要额外操作：
dp[i][j]=dp[i−1][j−1]dp[i][j]=dp[i−1][j−1]
2. 如果不同，我们可以进行三种操作：
- 替换：把 word1[i-1] 替换成 word2[j-1]，操作数+1，状态变为 dp[i-1][j-1] + 1
- 删除：删除 word1[i-1]，操作数+1，状态变为 dp[i-1][j] + 1
- 插入：在 word1 当前位置插入 word2[j-1]，操作数+1，状态变为 dp[i][j-1] + 1
取三者最小值：
dp[i][j]=min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])+1dp[i][j]=min(dp[i−1][j−1],dp[i−1][j],dp[i][j−1])+1
初始化：
-
dp[0][j] = j：空字符串变成 word2 前 j 个字符，需要插入 j 次。
-
dp[i][0] = i：word1 前 i 个字符变成空字符串，需要删除 i 次。
最终答案： dp[m][n]，其中 m = len(word1), n = len(word2)。
三、Java代码实现
class Solution {
public int minDistance(String word1, String word2) {
// 1. 获取两个字符串的长度
int size1 = word1.length();
int size2 = word2.length();
// 2. 定义dp数组，dp[i][j] 表示：
// 将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作数
// 注意：数组大小是 (size1+1) x (size2+1)，因为要包含空字符串的情况
int[][] dp = new int[size1 + 1][size2 + 1];
// 3. 初始化边界条件
// 3.1 当 word2 为空时（j=0），将 word1 的前 i 个字符全部删除
// 所以 dp[i][0] = i，需要删除 i 次
for (int i = 0; i <= size1; i++) {
dp[i][0] = i;
}
// 3.2 当 word1 为空时（i=0），将空字符串变成 word2 的前 j 个字符
// 所以 dp[0][j] = j，需要插入 j 次
for (int j = 0; j <= size2; j++) {
dp[0][j] = j;
}
// 4. 动态规划填表，从左上到右下逐行逐列计算
for (int i = 1; i <= size1; i++) {
for (int j = 1; j <= size2; j++) {
// 获取当前要比较的两个字符（注意索引从0开始，所以要减1）
char c1 = word1.charAt(i – 1);
char c2 = word2.charAt(j – 1);
// 4.1 如果这两个字符相同，则不需要任何操作
// 直接继承左上角的值：dp[i-1][j-1]
if (c1 == c2) {
dp[i][j] = dp[i – 1][j – 1];
} else {
// 4.2 如果字符不同，则考虑三种操作，取最小值后加1
// ① 插入：在 word1 当前位置插入 word2[j-1]，对应 dp[i][j-1] + 1
// ② 删除：删除 word1[i-1]，对应 dp[i-1][j] + 1
// ③ 替换：将 word1[i-1] 替换为 word2[j-1]，对应 dp[i-1][j-1] + 1
dp[i][j] = Math.min(
Math.min(dp[i][j – 1], // 插入
dp[i – 1][j]), // 删除
dp[i – 1][j – 1] // 替换
) + 1; // 三种操作任选一种，所以操作数加1
}
}
}
// 5. 返回最终结果：将完整的 word1 转换成完整的 word2 所需的最少操作数
// 即 dp 数组右下角的值
return dp[size1][size2];
}
}
四、运行结果
五、软考真题
#include<stdio.h>
#define N 100
char A[N]="CTGA";
char B[N]="ACGCTA";
int d[N][N];
int min(int a,int b){
return a<b?a:b;
}
int editdistance(char *str1,int len1,char *str2,int len2){
int i,j;
int diff;
int temp;
for(i=0;i<=len1;i++){
d[i][0]=i;
}
for(j=0;j<=len2;j++){
–(1)–;
}
for(i=1;i<=len1;j++){
for(j=1;j<=len2;j++){
if(–(2)–){
d[i][j]=d[i-1][j-1];
}else{
temp=min(d[i-1][j]+1,d[i][j-1]+1);
d[i][j]=min(temp,–(3)–);
}
}
}
return –(4)–
}
答案：
（1）：data[0][j]==j （2）：str1[i-1]==str2[j-1] （3）：d[i-1][j-1]+1 （4）：d[len1][len2]
（注意：这道题，完全就是力扣上的“编辑距离”原题，详见上面的代码）
以上就是本篇文章的全部内容，喜欢的话可以留个免费的关注呦~~~
