#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

提示

动态规划