没有合适的资源?快使用搜索试试~ 我知道了~
1.1 输入描述: 1.2 输出描述: 1.3 输入例子: 1.4 输出例子:
资源详情
资源评论
资源推荐
最短编辑距离
1/2
最短编辑距离
1 题目描述
UNIX 系统下有一个行编辑器 ed,它每次只对一行文本做删除一个字符、插入一个字符或替换
一个字符三种操作。例如某一行的内容是“ABC”,经过把第二个字符替换成“D”、删除第一个字
符、末尾插入一个字符“B”,这三步操作后,内容就变成了“DCB”。即“ABC”变成“DCB”需要
经过 3 步操作,我们称它们的编辑距离为 3。
现在给你两个任意字符串(不包含空格),请帮忙计算它们的最短编辑距离。
1.1 输入描述:
输入包含多组数据。每组数据包含两个字符串 m 和 n,它们仅包含字母,并且长度不超过 1024。
1.2 输出描述:
对应每组输入,输出最短编辑距离。
1.3 输入例子:
ABC CBCD
ABC DCB
1.4 输出例子:
2
3
2 解题思路
设 A 和 B 是 2 个字符串。要用最少的字符操作将字符串 A 转换为字符串 B。这里所说的字符操
作包括:
(1) 删除一个字符;
(2) 插入一个字符;
(3) 将一个字符改为另一个字符。
将字符串 A 变换为字符串 B 所用的最少字符操作数称为字符串 A 到 B 的编辑距离。设 A 的长
度为 m,B 的长度为 n 创建一个二维数组 d,大小为(m+1)*(n+1),来记录 a
1
-a
m
与 b
1
-b
n
之间的
我就是月下
- 粉丝: 25
- 资源: 336
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0