题目描述

给你两个字符串 str1 和 str2，请你计算出将 str1 转换成 str2 所使用的最少操作数 。

你可以对一个字符串进行如下三种操作：



	插入一个字符


	删除一个字符


	替换一个字符

输入格式

输入包含两行，第一行是字符串str1，第二行是字符串str2。其中str1和str2都是由小写英文字母组成的，这两个字符串的长度均不超过500。

输出格式

输出将str1转换成str2所使用的最少操作数。

horse
ros

3

提示

测试样例中的horse转化为ros至少需要三步： 1、horse -> rorse (将 'h' 替换为 'r') 2、rorse -> rose (删除 'r') 3、rose -> ros (删除 'e')