双序列型动态规划——编辑距离

忘是亡心i 2022-10-27 12:07 183阅读 0赞

#  #

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

你可以对一个单词进行如下三种操作：

插入一个字符  
删除一个字符  
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
    输出：3
    解释：
    horse -> rorse (将 'h' 替换为 'r')
    rorse -> rose (删除 'r')
    rose -> ros (删除 'e')

### 1、确定状态 ###

设A长度是m，B长度是n

全部操作完成后 A 的长度也是 n ，并且 A\[n-1\]=B\[n-1\]

于是最优策略最终都是让A的最后一个字符变成B 的最后一个字符。

按照题目描述，让A的最后一个字符变成B 的最后一个字符我们总共可以分为四种情况：

*  情况一：A在最后插入B\[n-1\]， 要将A\[0…m-1\]变成B\[0…n-2\]
 *  情况二：A最后一个字符替换成B\[n-1\]，要将A\[0…m-2\]变成B\[0…n-2\]
 *  情况三：A删掉最后一个字符，要将A\[0…m-2\]变成B\[0…n-1\]
 *  情况四：A和B最后一个字符相等，要将A\[0…m-2\]变成B\[0…n-2\]

因此，要求A\[0…m-1\]和B\[0…n-1\]的最小编辑距离，就需要求A\[0…m-1\]和B\[0…n-2\]的最小编辑距离，A\[0…m-2\]和B\[0…n-1\]的最小 编辑距离和A\[0…m-2\]和B\[0…n-2\]的最小编辑距离

所以可以假设f\[i\]\[j\]为A前i个字符A\[0…i-1\]和B前j个字符B\[0…j-1\]的最小编辑距离

### 2、转移方程 ###

f\[i\]\[j\]为A前i个字符A\[0…i-1\]和B前j个字符B\[0…j-1\]的最小编辑距离  
![在这里插入图片描述][20210203221825393.png]

### 3、初始条件和边界情况 ###

初始条件：一个空串和一个长度为L的串的最小编辑距离是L

– f\[0\]\[j\] = j (j = 0, 1, 2, …, n)

– f\[i\]\[0\] = i (i = 0, 1, 2, …, m)

### 4、计算顺序 ###

逐行计算，答案是f\[m\]\[n\]

时间复杂度：O(MN)，空间复杂度：O(MN)

### 5、代码实现 ###

class Solution(object):
        def minDistance(self, word1, word2):
            """ :type word1: str :type word2: str :rtype: int """
            n = len(word1) + 1
            m = len(word2) + 1
            dp = [[0] * m for i in range(n)]
            for i in range(n):
                for j in range(m):
                    if i == 0 and j == 0:
                        continue
                    if i == 0:
                        dp[i][j] = j
                        continue
                    if j == 0:
                        dp[i][j] = i
                        continue
                    dp[i][j] = min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1)
                    if word1[i - 1] == word2[j - 1]:
                        dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
            return dp[n - 1][m - 1]

#  #

[20210203221825393.png]: /images/20221024/e71f5b99a4594000b3c81e38f0a29b04.png