#1812. Edit
Edit
说明
有二个字串 str1, str2 , 字串str2 可以经过若于次变换后变成str1,其变换的规则是:
1) 可以在任何位置加入字符;
2) 可以删除任何字符;
3) 可以改变任何字符。
约定:增加、删除与改变任何一个字符称为一次变换。
例如:str1=‘bcadef ’ str2=’abcedkk’
可以经过的变换为:
1)删去第一个字符‘a’ str2=’bcedkk’
2)改变一个字符,将‘e’变成‘a’ str2=’bcadkk’
3)改变一个字符,将‘k’变成‘e’ str2=’bcadek’
4) 改变一个字符,将‘k’变成‘f’ str2=’bcadef’
此时,str2 经过4次变换后变成str1。
问题:给出str1,str2,要求用最少的变换次数从str2变换为str1 。
输入格式
多笔测资,每笔测资两行
第一行:字符串s1
第二行:字符串s2
输出格式
对每笔测资,输出一个整数,表示该组的最少变换次数。样例
bcadef
abcedkk
4