编辑距离

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

你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。

约定

• 每个操作代价均为 1。
• 两个单词可能为空。

输入

• word1、word2：字符串，长度 [0, 500]。

输出

最少操作数。

示例一

输入：

word1 = "horse", word2 = "ros"

输出：

3

解释：horse -> rorse（h→r）-> rose（删 r）-> ros（删 e）。

示例二

输入：

word1 = "intention", word2 = "execution"

输出：

5

示例三

输入：

word1 = "", word2 = "a"

输出：

1

复杂度要求

• 时间 O(m·n)，空间 O(m·n)。