首页 > 试题广场 >

最短编辑距离

[编程题]最短编辑距离
  • 热度指数:2023 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
UNIX系统下有一个行编辑器ed,它每次只对一行文本做删除一个字符、插入一个字符或替换一个字符三种操作。例如某一行的内容是“ABC”,经过把第二个字符替换成“D”、删除第一个字符、末尾插入一个字符“B”,这三步操作后,内容就变成了“DCB”。即“ABC”变成“DCB”需要经过3步操作,我们称它们的编辑距离为3。

现在给你两个任意字符串(不包含空格),请帮忙计算它们的最短编辑距离。

输入描述:
输入包含多组数据。

每组数据包含两个字符串m和n,它们仅包含字母,并且长度不超过1024。


输出描述:
对应每组输入,输出最短编辑距离。
示例1

输入

ABC CBCD
ABC DCB

输出

2
3