leetcode(力扣) 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’)

思路分析

题目中说请返回将 word1 转换成 word2 所使用的最少操作数 。

题目中规定了将word1转换成word2。

并且规定了增删改三种操作。

现在假设有两个字符串 ，A：dog 。B：doge

让A和B相同，则可以：

• A末尾添加一个e，变成doge。
• B删除末尾的e，变成dog

可以发现上述两种操作是等价的，注意这里是指操作次数等价，而不是值变化之后的结果等价。

同理，例如有 A：dg和B：de ，有两种情况让他们变得等价。

• 将A的末尾g变成e
• 将B的末尾e变成g

综上，删除和增加元素是等价的，替换元素也是等价的。

所以问题变成：

• 在A中删除一个字符
• 在B中删除一个字符 （等价于在A中插入一个字符）
• 替换A中的一个字符

老规矩，动态规划五步走;

1.确定dp数组下标含义：

dp[i][j] 表示 A字符串到下标i-1,B字符串到下标j-1 时的两个子串相等最小的编辑距离。

2.状态转移公式：

如果 A[i-1] == B[j-1] ：
此时两字符串末尾项一样，不需要增删改，直接继承之前的最小编辑距离就行了。dp[i][j]=dp[i−1][j−1]

如果 A[i-1] ！= B[j-1] ：

• 删A的一个元素，那么就是以下标 i−2为结尾的 A与j−1 为结尾的 B的最近编辑距离 再加上一个操作。最少操作次数为 dp[i−1][j]+1

• 删B的一个元素，那么就是以下标 i−1为结尾的 A与j−2 为结尾的 B的最近编辑距离 再加上一个操作。最少操作次数为 dp[i][j-1]+1

• 替换掉A的末尾元素 也就是 A[i-2]，使其等于B[j-2],那么就是以下标 i−2 为结尾的 word1 与 j−2 为结尾的 word2 的最近编辑距离 即 dp[i-1][j-1] 再加上一个替换元素的操作 ， dp[i-1][j-1]+1.

• 上面这三种操作都能让 子串A和B变得相同，那么取这三个中操作次数最小的即可。

完整代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

        dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)]


        for i in range(len(word1)+1):
            dp[i][0] = i
        for i in range(len(word2)+1):
            dp[0][i] = i

        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+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]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)
        print(dp)
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19