说明

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

输入格式

两行字符串，分别为word1与word2

输出格式

一个整数，即将 word1 转换成 word2 所使用的最少操作数 。

样例

horse
ros

3

提示

样例说明：

输入：word1 = "horse", word2 = "ros"

输出：3

解释：

horse -> rorse (将 'h' 替换为 'r') 

rorse -> rose (删除 'r') 

rose -> ros (删除 'e')

数据范围：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成