#P4100. 编辑距离
-
ID: 2337
Tried: 45
Accepted: 29
Difficulty: 2
编辑距离
题目描述
给定两个单词 word1 和 word2，请返回将 word1 转换为 word2 所需的最少操作数。
允许的操作如下：
- 插入 一个字符
- 删除 一个字符
- 替换 一个字符
输入描述
输入包含两行：
- 第一行是字符串
word1（0≤∣word1∣≤500）。 - 第二行是字符串
word2（0≤∣word2∣≤500）。
word1 和 word2 仅由小写英文字母组成。
输出描述
输出一行，表示将 word1 转换为 word2 所需的最少操作数。
样例输入 1
horse
ros
样例输出 1
3
说明：
horse → rorse（替换h→r）rorse → rose（删除r）rose → ros（删除e）
样例输入 2
intention
execution
样例输出 2
5
说明：
intention → inention（删除t）inention → enention（替换i→e）enention → exention（替换n→x）exention → exection（替换n→c）exection → execution（插入u）
解题思路：动态规划
-
定义状态
设 dp[i][j] 表示 将word1[0:i]转换为word2[0:j]需要的最少操作数。 -
状态转移方程
-
如果
dp[i][j]=dp[i−1][j−1]word1[i-1] == word2[j-1]（最后一个字符相同，不需要操作）： -
如果
word1[i-1] \neq word2[j-1]（最后一个字符不同，需要操作）：
我们可以进行 插入、删除、替换 三种操作：- 插入
word2[j-1]（相当于word1长度不变，word2长度减少）：
dp[i][j]=dp[i][j−1]+1 - 删除
word1[i-1]（相当于word1长度减少，word2长度不变）：
dp[i][j]=dp[i−1][j]+1 - 替换
word1[i-1]为word2[j-1]（相当于word1长度减少，word2长度减少）：
dp[i][j]=dp[i−1][j−1]+1
取最小值：
$$dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 $$ - 插入
-
-
初始化
dp[i][0] = i（将word1[0:i]变为空字符串，需要i次删除）dp[0][j] = j（将空字符串变为word2[0:j]，需要j次插入）
-
最终答案
dp[m][n]即word1[0:m]变为word2[0:n]所需的最少操作数。 -
时间复杂度 O(m×n)
-
空间复杂度 O(m×n)
Python 代码
import sys
def min_edit_distance(word1, word2):
""" 使用动态规划计算编辑距离 """
m, n = len(word1), len(word2)
# 初始化 DP 数组，dp[i][j] 表示 word1[0:i] 转换为 word2[0:j] 需要的最少操作数
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 处理边界情况
for i in range(m + 1):
dp[i][0] = i # 将 word1[0:i] 转换为空字符串，需要 i 次删除
for j in range(n + 1):
dp[0][j] = j # 将空字符串转换为 word2[0:j]，需要 j 次插入
# 填充 DP 表
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]: # 字符相同，不需要操作
dp[i][j] = dp[i - 1][j - 1]
else: # 选择 插入、删除、替换 中的最小操作数
dp[i][j] = min(dp[i - 1][j], # 删除
dp[i][j - 1], # 插入
dp[i - 1][j - 1] # 替换
) + 1
return dp[m][n] # 返回最小编辑距离
def main():
""" 读取输入并调用求解函数 """
word1 = sys.stdin.readline().strip()
word2 = sys.stdin.readline().strip()
print(min_edit_distance(word1, word2))
if __name__ == "__main__":
main()
Java 代码
import java.util.*;
public class Main {
public static int minEditDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
// 初始化 DP 数组
int[][] dp = new int[m + 1][n + 1];
// 处理边界情况
for (int i = 0; i <= m; i++) {
dp[i][0] = i; // word1[0:i] 变为空字符串，删除 i 次
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j; // 空字符串变为 word2[0:j]，插入 j 次
}
// 填充 DP 表
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1]; // 字符相同，不需要操作
} else {
dp[i][j] = Math.min(dp[i - 1][j], // 删除
Math.min(dp[i][j - 1], // 插入
dp[i - 1][j - 1] // 替换
)) + 1;
}
}
}
return dp[m][n]; // 返回最小编辑距离
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String word1 = sc.next();
String word2 = sc.next();
System.out.println(minEditDistance(word1, word2));
sc.close();
}
}
C++ 代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int minEditDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
// 初始化 DP 数组
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 处理边界情况
for (int i = 0; i <= m; i++) {
dp[i][0] = i; // word1[0:i] 变为空字符串，删除 i 次
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j; // 空字符串变为 word2[0:j]，插入 j 次
}
// 填充 DP 表
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // 字符相同，不需要操作
} else {
dp[i][j] = min({dp[i - 1][j], // 删除
dp[i][j - 1], // 插入
dp[i - 1][j - 1] // 替换
}) + 1;
}
}
}
return dp[m][n]; // 返回最小编辑距离
}
int main() {
string word1, word2;
cin >> word1 >> word2; // 读取两个输入字符串
cout << minEditDistance(word1, word2) << endl;
return 0;
}