1 题目

72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

2 理解 题解

涉及到字符串的题目，十有八九是动态规划，而且几乎都是二维的。解决动态规划问题三要素：

（1）找出dp[] 元素的定义，题目一般非常隐晦。

（2）找出递推关系。dp[n] = $f($ dp[n-1] $)$ 。 即是 状态转移方程。

（3）找出初始状态。

编辑距离的题解理解：

（1）将编辑理解到位，简化为在单词 A 中插入一个字符、在单词 B 中插入一个字符、修改单词 A 的一个字符。

（2）由空字符串开头给初始状态。

（3）找出了状态转移方程。

3 程序

只要有状态转移方程，动态规划的程序好写：

注意，dp比word长度多1，因为dp里面存着初始数值。

python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if not len(word1) * len(word2):
            return len(word1) + len(word2)
        # 初始状态
        dp = [[0 for _ in range(len(word1) + 1)] for _ in range(len(word2) + 1)]
        dp[0] = [i for i in range(len(word1) + 1)]
        for i in range(len(word2) + 1):
            dp[i][0] = i
        # 状态转移方程计算其余的状态
        for m in range(len(word2)):  # 每一行
            for n in range(len(word1)):  # 每一列
                i = m + 1
                j = n + 1
                # dp[i - 1][j]+1 在word1中插入一个变成word2
                # dp[i - 1][j]+1 在word2中插入一个变成word1
                # dp[i - 1][j - 1]+1 在word1中修改一个变成word2
                if word1[n] == word2[m]:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] - 1)
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
        return dp[-1][-1]