72. 编辑距离

leetcode python 字符串动态规划困难

LeetCode

发布日期: 2020-10-21

更新日期: 2020-10-22

文章字数: 1.1k

阅读时长: 4 分

阅读次数:

一、题目

给你两个单词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')

二、思路

1. 动态规划

题目中告诉我们对一个单词可以进行增、删、改三种操作。那接下来就先上个表吧，依然采用题目中的例子word1 = "horse"、word2 = "ros"。表格如下：

	#	r	o	s
#	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3

接下来，就是结合表格来进行详解：

表格中的#所对应的行和列分别对应着word1和word2为空串的情况。

首先我们定义一个二维数组dp，这里的dp数组便与上述表格相对应。数组中的每一个位置的意思便是word1[:i]子串转换为word2[:j]子串需要的编辑距离。

实际上，通过上述表格的数据，我们便可以发现将原问题转化为子问题以后的结果之间的关系。

我们用两个子串A = hors，B = ro来举列子:

我们选择子串hor和r，将hor转换为r编辑距离为2。因为最后一个单词相同，所以只需要将删除h和o两步操作即可。
将hors转为为r，只需要h、o、s三步删除操作即可。
当目标单词为ro，将hor转换为ro，需要将h转换为r，并且将r删除两步操作即可。
最后，我们可以对比这几种情况与A转换为B进行比对：
- A 、B与第一种情况相比，hor增加了s，r增加了o。两个单词都增加了一个字母，所以只需要将s更改为o一步操作即可实现A转换为B。编辑距离不会大于2+1。
- A 、B与第二种情况相比，r增加了o。所以需要实现A转换为B，编辑距离不会大于3+1。
- A 、B与第三种情况相比，单词hor增加一个s，所以只需删除s一步操作即可实现A转换为B。编辑距离不会大于2+1。

所以可以得出dp[i][j]与dp[i-1][j]、dp[i-1][j-1]、dp[i][j-1]这三个位置都有关系，并且dp[i][j]位置的编辑距离都不大于这三个位置编辑距离加1。所以我们只需要取其中的最小值即可。

对于结尾字幕相同的单词，这时转换的编辑距离实际上只需要考虑相同字母之前的子串的转换编辑距离即可。

最后，我们可以得出状态转移方程：

最后一个字母不同的情况下：
$$
dp[i][j] = min(dp[i-1][], dp[i][j-1], dp[i-1][j-1]) + 1
$$
最后一个字母相同的情况下：
$$
dp[i][j] = dp[i-1][j-1]
$$

对于边界条件，当word1为空串、word2不为空串时，编辑距离就等于word2的长度n，相当于对word1执行了n次插入操作；当word2为空串、word1不为空串时，编辑距离等于word1的长度m，相当于对word1执行了m次删除操作；当word1与word2同时为空，则不需要任何编辑操作，编辑距离为0。

最后将dp[m][n]返回即可。

三、代码

1. 动态规划

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m  = len(word1)
        n = len(word2)
        # 创建dp数组
        dp = [[0]*(n+1) for _ in range(m+1)]

        # 为dp数组赋初值
        for j in range(n+1):
            dp[0][j] = j
        for i in range(m+1):
            dp[i][0] = i

        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
        return dp[m][n]