题目0072:编辑距离

题目描述

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

解题技巧

• 方法一:动态规划

我们可以对任意一个单词进行三种操作:

插入一个字符;

删除一个字符;

替换一个字符。

题目给定了两个单词,设为A和B,这样我们就能够六种操作方法。但我们可以发现,如果我们有单词A和单词B:

• 对单词A删除一个字符和对单词B插入一个字符是等价的。例如当单词A为doge,单词B为dog时,我们既可以删除单词A的最后一个字符e,得到相同的dog,也可以在单词B末尾添加一个字符e,得到相同的doge;
• 同理,对单词B删除一个字符和对单词A插入一个字符也是等价的;
• 对单词A替换一个字符和对单词B替换一个字符是等价的。例如当单词A为bat,单词B为cat时,我们修改单词A的第一个字母b -> c,和修改单词B的第一个字母c -> b是等价的。

这样以来,本质不同的操作实际上只有三种:

在单词A中插入一个字符;

在单词B中插入一个字符;

修改单词A的一个字符。

这样以来,我们就可以把原问题转化为规模较小的子问题。我们用A = horse,B = ros 作为例子,来看一看是如何把这个问题转化为规模较小的若干子问题的。

在单词A中插入一个字符 :如果我们知道horse到ro的编辑距离为a,那么显然horse到ros的编辑距离不会超过a + 1。这是因为我们可以在a次操作后将horse和ro变为相同的字符串,只需要额外的1次操作,在单词A的末尾添加字符s,就能在a + 1次操作后将horse和ro变为相同的字符串;

在单词B中插入一个字符 :如果我们知道hors到ros的编辑距离为b,那么显然horse到ros的编辑距离不会超过b + 1,原因同上;

修改单词A的一个字符 :如果我们知道hors到ro的编辑距离为c,那么显然horse到ros的编辑距离不会超过c + 1,原因同上。

那么从horse变成ros的编辑距离应该为min(a+1,b+1,c+1)。

注意:为什么我们总是在单词A和B的末尾插入或者修改字符,能不能在其它的地方进行操作呢?答案是可以的,但是我们知道,操作的顺序是不影响最终的结果的。例如对于单词cat,我们希望在c和a之间添加字符d并且将字符t修改为字符b,那么这两个操作无论为什么顺序,都会得到最终的结果cdab。

你可能觉得horse到ro这个问题也很难解决。但是没关系,我们可以继续用上面的方法拆分这个问题,对于这个问题拆分出来的所有子问题,我们也可以继续拆分,直到:

字符串A为空,如从转换到ro,显然编辑距离为字符串B的长度,这里是2;

字符串B为空,如从horse转换到,显然编辑距离为字符串A的长度,这里是5。

因此,我们就可以使用动态规划来解决这个问题了。我们用D[i][j]表示A的前i个字母和B的前j个字母之间的编辑距离。

如上所述,当我们获得D[i][j-1],D[i-1][j]和D[i-1][j-1]的值之后就可以计算出 D[i][j]。

D[i][j-1]为A的前i个字符和B的前j-1个字符编辑距离的子问题。即对于B的第j个字符,我们在A的末尾添加了一个相同的字符,那么D[i][j]最小可以为D[i][j-1]+1;

D[i-1][j]为A的前i-1个字符和B的前j个字符编辑距离的子问题。即对于A的第i个字符,我们在B的末尾添加了一个相同的字符,那么D[i][j]最小可以为D[i-1][j]+1;

D[i-1][j-1]为A前i-1个字符和B的前j-1个字符编辑距离的子问题。即对于B的第j个字符,我们修改A的第i个字符使它们相同,那么D[i][j]最小可以为D[i-1][j-1]+1。特别地,如果A的第i个字符和B的第j个字符原本就相同,那么我们实际上不需要进行修改操作。在这种情况下,D[i][j]最小可以为D[i-1][j-1]。

那么我们可以写出如下的状态转移方程:

若A和B的最后一个字母相同:

$$\begin{aligned} D[i][j] &= \min(D[i][j-1] + 1, D[i-1][j]+1, D[i-1][j-1])\\ &= 1 + \min(D[i][j - 1], D[i-1][j], D[i-1][j-1] - 1) \end{aligned}$$

若A和B的最后一个字母不同:

$$D[i][j] = 1 + \min(D[i][j-1], D[i-1][j], D[i-1][j-1])$$

所以每一步结果都将基于上一步的计算结果,示意如下:

对于边界情况,一个空串和一个非空串的编辑距离为D[i][0]=i和D[0][j]=j,D[i][0]相当于对word1执行i次删除操作,D[0][j]相当于对word1执行j次插入操作。

综上我们得到了算法的全部流程。

class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        n = len(word1)
        m = len(word2)

        # 有一个字符串为空串
        if n * m == 0:
            return n + m

        # DP 数组
        D = [ [0] * (m + 1) for _ in range(n + 1)]

        # 边界状态初始化
        for i in range(n + 1):
            D[i][0] = i
        for j in range(m + 1):
            D[0][j] = j

        # 计算所有 DP 值
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                left = D[i - 1][j] + 1
                down = D[i][j - 1] + 1
                left_down = D[i - 1][j - 1] 
                if word1[i - 1] != word2[j - 1]:
                    left_down += 1
                D[i][j] = min(left, down, left_down)

        return D[n][m]

复杂度分析:

时间复杂度:$O(mn)$,其中m为word1的长度,n为word2的长度。

空间复杂度:$O(mn)$,我们需要大小为$O(mn)$的D数组来记录状态值。