P2758「编辑距离」
P2758「编辑距离」
hotarugali
发布于 2022-03-13 11:48:58
发布于 2022-03-13 11:48:58
1. 题目
题目链接：P2758「编辑距离」 。
题目描述
设 A 和 B 是两个字符串。我们要用最少的字符操作次数，将字符串 A 转换为字符串 B 。这里所说的字符操作共有三种：
- 删除一个字符；
- 插入一个字符；
- 将一个字符改为另一个字符；
！皆为小写字母！
输入格式
第一行为字符串 A ；第二行为字符串 B ；字符串 A 和 B 的长度均小于 2000 。
输出格式
只有一个正整数，为最少字符操作次数。
输入输出样例
输入 #1
sfdqxbw
gfdgw输出 #1
42. 题解
分析
易知编辑距离是对称的，即将字符串 A 变成字符串 B 和将字符串 B 变成字符串 A 所需的最小操作数是一样的，也就是字符串 A 、B 之间的编辑距离。然后直觉感觉就是一道简单的 dp 题：
- 假设 f[i][j] 表示字符串 A[0..i-1] 和 B[0..j-1]
之间的编辑距离，则有如下转移方程：
- 如果A[i] = B[j] ，则 f[i][j] = f[i-1][j-1] 。
- 如果 A[i] \neq B[j] ，则 f[i][j] = \min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1 。
- 边界条件为：f[0][0] = 0, f[i][0] = i, f[0][j] = j 。
代码
# 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;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-01-19，如有侵权请联系 cloudcommunity@tencent.com 删除
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号