0072. 编辑距离

0072. 编辑距离 #

  • 标签:字符串、动态规划
  • 难度:困难

题目大意 #

给定两个单词 word1word2,计算出将 word1 转换为 word2 所使用的最少操作数。

对一个单词可以进行以下三种操作:

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

解题思路 #

动态规划求解。

先定义状态 dp[i][j] 为以 i - 1 为结尾的字符串 word1 变为以 j - 1 字结尾的字符串 word2 ,所使用的最少操作次数。

然后确定状态转移方程。

  • 如果 word1[i - 1] == word2[j - 1],无需插入、删除、替换。dp[i][j] 取源于以 i - 2 结尾结尾的字符串 word1 变为 j - 1 结尾的字符串 word2,即 dp[i][j] = dp[i - 1][j - 1]
  • 如果 word1[i - 1] != word2[j - 1]dp[i][j] 取源于以下三种情况中的最小情况:
    • word1i - 1 位置上插入一个元素(等价于 word2 删除一个元素),最少操作次数依赖于以 i - 2 结尾的字符串 word1 变为以 j - 1 结尾的字符串 word2,再加上插入需要的操作数 1,即:dp[i - 1][j] + 1
    • word2j - 1 位置上插入一个元素(等价于 word1 删除一个元素),最少操作次数依赖于以 i - 1 结尾的字符串 word1 变为以 j - 2 结尾的字符串 word2,再加上插入需要的操作数 1,即:dp[i][j - 1] + 1
    • word1[i - 1] 替换为 word2[j - 1],最少操作次数依赖于以 i - 2 结尾的字符串 word1 变为以 j - 2 结尾的字符串 word2,再加上替换的操作数 1,即:dp[i - 1][j - 1] + 1

然后确定一下边界条件。

  • word1 为空字符串,以 j - 1 结尾的字符串 word2 要删除 j 个字符才能和 word1 相同,即 dp[0][j] = j
  • word2 为空字符串,以 i - 1 结尾的字符串 word1 要删除 i 个字符才能和 word2 相同,即 dp[i][0] = i

最后递推求解,最终输出 dp[size1][size2] 为答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        size1 = len(word1)
        size2 = len(word2)
        dp = [[0 for _ in range(size2 + 1)] for _ in range(size1 + 1)]

        for i in range(size1 + 1):
            dp[i][0] = i
        for j in range(size2 + 1):
            dp[0][j] = j
        for i in range(1, size1 + 1):
            for j in range(1, size2 + 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 - 1][j], dp[i][j - 1]) + 1
        return dp[size1][size2]
本站总访问量  次  |  您是本站第  位访问者