P2758「编辑距离」

1. 题目

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

题目描述

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

1、删除一个字符;

2、插入一个字符;

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

!皆为小写字母!

输入格式

第一行为字符串A;第二行为字符串B;字符串A和B的长度均小于2000。

输出格式

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

输入输出样例

输入 #1

1
2
sfdqxbw
gfdgw

输出 #1

1
4

2. 题解

分析

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

  • 假设 f[i][j] 表示字符串 A[0..i-1] 和 B[0..j-1] 之间的编辑距离,则有如下转移方程:
  1. 如果 A[i] == B[j],则 f[i][j] = f[i-1][j-1]。
  2. 如果 A[i] != B[j],则 f[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] = 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;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!