本文共 2331 字，大约阅读时间需要 7 分钟。

题目：（中等）

标签：字符串、动态规划、动态规划-状态表格

LeetCode的Python执行用时随缘，只要时间复杂度没有明显差异，执行用时一般都在同一个量级，仅作参考意义。

解法一（动态规划）：

class Solution:    def minDistance(self, word1: str, word2: str) -> int:        # 生成状态表格        N1, N2 = len(word1), len(word2)        matrix = [[0] * (N1 + 1) for _ in range(N2 + 1)]        # 填写首行首列        for j in range(1, N1 + 1):            matrix[0][j] = matrix[0][j - 1] + 1        for i in range(1, N2 + 1):            matrix[i][0] = matrix[i - 1][0] + 1        # 状态计算        for i in range(1, N2 + 1):            for j in range(1, N1 + 1):                if word2[i - 1] != word1[j - 1]:                    matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1]) + 1                else:                    matrix[i][j] = matrix[i - 1][j - 1]        return matrix[-1][-1]

解法二（单行动态规划）：

class Solution:    def minDistance(self, word1: str, word2: str) -> int:        # 生成状态表格        N1, N2 = len(word1), len(word2)        matrix = [0] * (N1 + 1)        # 填写首行首列        for j in range(1, N1 + 1):            matrix[j] = matrix[j - 1] + 1        # 状态计算        for i in range(1, N2 + 1):            last = matrix[0]            matrix[0] += 1            for j in range(1, N1 + 1):                tmp = matrix[j]                if word2[i - 1] != word1[j - 1]:                    matrix[j] = min(matrix[j], matrix[j - 1]) + 1                else:                    matrix[j] = last                last = tmp        return matrix[-1]

解法三（计算相同子序列）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gcONmcxT-1597633134346)(LeetCode题解(0583)]：截图1.png)

class Solution:    def minDistance(self, word1: str, word2: str) -> int:        # 生成状态表格        N1, N2 = len(word1), len(word2)        matrix = [0] * (N1 + 1)        # 状态计算        for i in range(1, N2 + 1):            last = 0            for j in range(1, N1 + 1):                tmp = matrix[j]                if word2[i - 1] == word1[j - 1]:                    matrix[j] = last + 1                else:                    matrix[j] = max(matrix[j], matrix[j - 1])                last = tmp        # 生成结果        return N1 + N2 - 2 * matrix[-1]

转载地址：https://dataartist.blog.csdn.net/article/details/108051563 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！