每日一题之两个字符串的删除操作-Toy模板网

这篇具有很好参考价值的文章主要介绍了每日一题之两个字符串的删除操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 **相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

我们可以定义一个二维数组dp，其中dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最小步数。

首先，我们需要考虑边界情况，当word1和word2的长度分别为零时，它们已经相同了，所以dp[0][0] = 0。当word1为空字符串，而word2不为空时，则需要删除word2中的所有字符，所以dp[0][j] = j。同理，当word2为空字符串，而word1不为空时，需要删除word1中的所有字符，所以dp[i][0] = i。

接下来，我们考虑状态转移方程。假设我们要计算dp[i][j]，即将word1的前i个字符转换为word2的前j个字符所需的最小步数。我们有以下几种情况：

如果word1[i-1]等于word2[j-1]，即当前字符相等，那么不需要进行删除操作，所以dp[i][j] = dp[i-1][j-1]。
如果word1[i-1]和word2[j-1]不相等，那么我们有两种选择：
- 删除word1[i-1]字符，然后将word1的前i-1个字符转换为word2的前j个字符，所以dp[i][j] = 1 + dp[i-1][j]。
- 删除word2[j-1]字符，然后将word1的前i个字符转换为word2的前j-1个字符，所以dp[i][j] = 1 + dp[i][j-1]。综上所述，我们可以得到状态转移方程：
```
if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])
```

最后，我们可以通过填充dp数组来计算所需的最小步数。最终的结果即为dp[len(word1)][len(word2)]。文章来源地址https://www.toymoban.com/news/detail-609058.html

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n+1) for _ in range(m+1)]  # 初始化dp数组

    # 初始化边界情况
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j

    # 计算dp数组
    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])

    return dp[m][n]