UNIX系统下有一个行编辑器ed,它每次只对一行文本做删除一个字符、插入一个字符或替换一个字符三种操作。例如某一行的内容是“ABC”,经过把第二个字符替换成“D”、删除第一个字符、末尾插入一个字符“B”,这三步操作后,内容就变成了“DCB”。即“ABC”变成“DCB”需要经过3步操作,我们称它们的编辑距离为3。
现在给你两个任意字符串(不包含空格),请帮忙计算它们的最短编辑距离。
输入包含多组数据。
每组数据包含两个字符串m和n,它们仅包含字母,并且长度不超过1024。
对应每组输入,输出最短编辑距离。
ABC CBCD ABC DCB
2 3
这道题你会答吗?花几分钟告诉大家答案吧!