该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

增：插入一个字符 删：删除一个字符 改：替换一个字符

输入格式：

输入为两行，两个全部由小写英文字母组成的字符串 $word1$ 和 $word2$。 $0 <= word1.length, word2.length <= 500$

输出格式：

输出一个整数表示最少操作数。

输入用例

horse
ros

输出用例

3

输入用例

intention
execution

输出用例

5

用例说明

对于样例一：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
对于样例二：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示

无