题目描述
给给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
示例 2：
提示：
- 0 <= word1.length, word2.length <= 500
- word1 和 word2 由小写英文字母组成
题目解析
解决两个字符串的动态规划问题，一般都是用两个指针 i, j 分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。
对于每对儿字符 s1[i] 和 s2[j]，可以有四种操作：
那么「状态」就是指针 i, j 的位置，「选择」就是上述的四种操作。
如果使用自底向上的迭代解法，这样定义 dp 数组：dp[i-1][j-1] 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离。dp 数组索引至少是 0，所以索引会偏移一位。
然后把上述四种选择用 dp 函数表示出来，就可以得出最后答案了。
参考代码
以下为 Java 代码。
递归解法
迭代解法
复杂度分析
- 时间复杂度 ：O(mn)，其中 m 为 word1 的长度，nnn 为 word2 的长度。
- 空间复杂度 ：O(mn)，我们需要大小为 O(mn) 的 数组来记录状态值。
