编辑距离
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
设 和 是两个字符串。要用最少的字符操作次数，将字符串 转换为字符串 。字符操作共有三种：
- 删除一个字符；
- 插入一个字符；
- 将一个字符改为另一个字符。
对任意两个字符串 和 ，计算出将 变换为 所用的最少操作次数。
输入格式
第一行：字符串 。
第二行：字符串 。
输出格式
一行，一个正整数，表示最少操作次数。
样例
sfdqxbw
gfdgw
4
样例解释
，。
一种最优方案为：
- 将
's'改为'g'， 变为gfdqxbw； - 将
'q'改为'g'， 变为gfdgxbw； - 删除
'x'， 变为gfdgbw； - 删除
'b'， 变为gfdgw。
共 步。
数据范围
- 字符串 和 的长度均小于 。