题目描述

给定两个字符串 S1 和 S2 （1 < S1长度 < 100 ，1 < S2长度 < 100 ），然后按照以下三种操作，将 S1 转为 S2 ，问最少操作几次可以完成。

对字符串可进行以下三种操作：

1. 插入一个字符；

2. 删除一个字符；

3. 修改一个字符。

例如：

S1 = abcd ，S2 = ebde ，S1 转为 S2 最少需要操作 3 次：

第一次操作：将 abcd 中的字符 a 修改成 e ，修改后为 ebcd ;

第二次操作：将 ebcd 中的字符 c 删除，删除后为 ebd ;

第三次操作：在 ebd 末端插入字符 e ，插入后为 ebde ；

经过 3 次操作，字符串 abcd 转为字符串 ebde 。

输入格式

第一行输入一个字符串 S1（1 < S1长度 < 100 ）

第二行输入一个字符串S2（ 1 < S2长度 < 100 ）

输出格式

一个整数，表示将 S1 转为 S2 的最少操作次数

样例

abcd
ebde

3