题目内容

对一个单词进行变换时，每一次操作可以选择以下三种动作之一：

• 在任意位置插入一个字符；
• 删除一个字符；
• 将某个字符替换成另一个字符。

给定初始单词 word1 和目标单词 word2，请计算把 word1 变为 word2 至少需要执行多少次操作。

约束条件

• 两个单词的长度均不超过 500。
• 两个单词仅由小写英文字母组成。

输入描述

输入包含两个参数：

• 字符串 word1，表示初始单词；
• 字符串 word2，表示目标单词。

输出描述

返回一个整数，表示将 word1 转换为 word2 所需的最少操作数。

样例1

输入

abc
yabd

输出

2

说明

将 abc 变为 yabd 最少需要 2 次操作。

先在开头插入字符 y，得到 yabc；再把末尾的 c 替换为 d，得到 yabd。因此最少操作数为 2。

样例2

输入

kitten
sitting

输出

3

说明

将 kitten 变为 sitting 最少需要 3 次操作。

先将 k 替换为 s，得到 sitten；再将 e 替换为 i，得到 sittin；最后在末尾插入 g，得到 sitting。因此最少操作数为 3。