1. 题目

题目链接:P2758「编辑距离」

题目描述

AABB 是两个字符串。我们要用最少的字符操作次数,将字符串 AA 转换为字符串 BB。这里所说的字符操作共有三种:

  1. 删除一个字符;

  2. 插入一个字符;

  3. 将一个字符改为另一个字符;

!皆为小写字母!

输入格式

第一行为字符串 AA;第二行为字符串 BB;字符串 AABB 的长度均小于 20002000

输出格式

只有一个正整数,为最少字符操作次数。

输入输出样例

输入 #1

1
2
sfdqxbw
gfdgw

输出 #1

1
4

2. 题解

分析

易知编辑距离是对称的,即将字符串 AA 变成字符串 BB 和将字符串 BB 变成字符串 AA 所需的最小操作数是一样的,也就是字符串 AABB 之间的编辑距离。然后直觉感觉就是一道简单的 dp 题:

  • 假设 f[i][j]f[i][j] 表示字符串 A[0..i1]A[0..i-1]B[0..j1]B[0..j-1] 之间的编辑距离,则有如下转移方程:
  1. 如果 A[i]=B[j]A[i] = B[j],则 f[i][j]=f[i1][j1]f[i][j] = f[i-1][j-1]
  2. 如果 A[i]B[j]A[i] \neq B[j],则 f[i][j]=min(f[i1][j1],f[i1][j],f[i][j1])+1f[i][j] = \min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1
  3. 边界条件为:f[0][0]=0,f[i][0]=i,f[0][j]=jf[0][0] = 0, f[i][0] = i, f[0][j] = j

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# include <bits/stdc++.h>
# define MAXLEN 2005
using namespace std;

char a[MAXLEN], b[MAXLEN];
int f[MAXLEN][MAXLEN];

int main()
{
scanf("%s%s", a, b);
int alen = strlen(a);
int blen = strlen(b);
f[0][0] = 0;
for(int i = 1; i <= alen; ++i) {
f[i][0] = i;
}
for(int j = 1; j <= blen; ++j) {
f[0][j] = j;
}
for(int i = 1; i <= alen; ++i) {
for(int j = 1; j <= blen; ++j) {
if(a[i-1] == b[j-1]) {
f[i][j] = f[i-1][j-1];
} else {
f[i][j] = min(f[i-1][j], min(f[i][j-1], f[i-1][j-1])) + 1;
}
}
}
int ans = f[alen][blen];
printf("%d\n", ans);
return 0;
}