题解 | #牛群编号变更#

• 题目考察的知识点 : 动态规划
• 题目解答方法的文字分析：

1. 使用最长公共子序列算法（Longest Common Subsequence）求出字符串 word1 和字符串 word2 的最长公共子序列的长度 overlap
2. 将两个字符串同时缩短到长度为 overlap，再分别在两个字符串中插入、删除或替换字符，使得两个字符串变成相同的字符串。这样操作的次数为 min(m−overlap,n−overlap)，每次操作需要修改两个字符串中的一个字符，因此总共需要修改 2min(m−overlap,n−overlap) 次。接着，如果两个字符串的长度不同，则需额外进行 ∣m−n∣ 次插入或删除操作。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param word1 string字符串
# @param word2 string字符串
# @return int整型
#
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        overlap = self.longestCommonSubsequence(word1, word2)
        return abs(m - n) + min(m - overlap, n - overlap) * 2

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[m][n]