最短编辑距离=三种语言
我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
给定两个字符串 A 和 B,现在要将 A 经过若干操作变为 B,可进行的操作有:
删除–将字符串 A 中的某个字符删除。
插入–在字符串 A 的某个位置插入某个字符。
替换–将字符串 A 中的某个字符替换为另一个字符。
现在请你求出,将 A 变为 B 至少需要进行多少次操作。
1.算法细节
- 这道题和之前的dp都有些不同,是一个完全匹配的dp赋值。这种赋值是怎么实现的呢?
以最长公共子序列为例子,dp[i][j]
存储的是a[1 ~ i]和b[1 ~ j]当中元素可选可不选的情况下,属性max最长的公共子序列
而本题的dp[i][j]
存储的是由a[1 ~ i]整个序列,经过属性min的最少次操作,可以化为b[1 ~ j]
dp[i][j]
的状态表示分为哪些?又是为何而分?
三个操作:删除,增加,修改,他们想要实现的条件各不相同,故根据此步所得前一步操作不同可划分为三个子集
1. 删除: 此时a[1 ~ i-1]
与b[1 ~ j]
匹配,多出来的a[i]
赘余,经过一部a[i]
的删除操作即可:dp[i-1][j] + 1
2. 增加: 此时a[1 ~ i]
与b[1 ~ j-1]
匹配,而b[i]
多出来后,为了达成匹配显然经过一部a[i]
的增加操作即可:dp[i][j-1] + 1
3. 修改: 此时a[1 ~ i-1]
与b[1 ~ j-1]
匹配,但是a[i]
与b[j]
相等与否,决定着我们是否要增加操作
a[i] == b[j] -> dp[i-1][j-1]
a[i] != b[j] -> dp[i-1][j-1] + 1
- 找寻max和min之前,如果这个依赖操作涉及到i-1,需要从1开始赋值,其次初始化也应该有INF或-INF,以及对于基础状态表达式的赋值工作
2.具体代码
java
import java.util.*;
public class Main {
static int N = 1010;
public static void main(String [] args) {
Scanner sc = new Scanner(System.in);
int[][] f = new int[N][N];
int n = sc.nextInt();
String A = " " + sc.next();
char []a = A.toCharArray();
int m = sc.nextInt();
String B = " " + sc.next();
char []b = B.toCharArray();
//添加
for(int i=1; i<=m; i++) f[0][i] = i;
//删除
for(int i=1; i<=n; i++) f[i][0] = i;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++){
if (a[i] == b[j]) f[i][j] = Math.min(Math.min(f[i-1][j] + 1, f[i][j-1] + 1), f[i-1][j-1]);
else f[i][j] = Math.min(Math.min(f[i-1][j], f[i][j-1]), f[i-1][j-1]) + 1;
}
System.out.println(f[n][m]);
}
}
python3
N = 1010
f = [[0]*N for _ in range(N)]
n = int(input())
a = " " + input()
m = int(input())
b = " " + input()
# 将 A 的前0个字母全部变成 B 的前m个字母,只能添加
for i in range(1,m+1):
f[0][i] = i
# 将 A 的前n个字母全部变成 B 的前0个字母,只能删除
for i in range(1,n+1):
f[i][0] = i
for i in range(1,n+1):
for j in range(1,m+1):
if a[i] == b[j]:
f[i][j] = min(f[i-1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1])
else:
f[i][j] = min(f[i-1][j] + 1, f[i][j - 1] + 1, f[i - 1][j - 1] + 1)
print(f[n][m])
C++
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
char a[N], b[N];
int n, m, dp[N][N];
int main(){
scanf("%d%s", &n, a+1);
scanf("%d%s", &m, b+1);
//求最小值:必须先初始化为无穷大
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
dp[i][j] = INF;
//先将dp的起溯源头:(删,增)初始化
for(int i=1; i<=n; i++) dp[i][0] = i;
for(int i=1; i<=m; i++) dp[0][i] = i;
//依次搜索
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++){
//先赋值(删,增)
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1);
if(a[i] == b[j]) dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
else dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1);
}
cout << dp[n][m] << endl;
return 0;
}