美文网首页
LeetCode 583. 两个字符串的删除操作

LeetCode 583. 两个字符串的删除操作

作者: 草莓桃子酪酪 | 来源:发表于2022-08-15 05:52 被阅读0次
题目

给定两个单词 word1 和 word2 ,返回使得 word1 和 word2 相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。

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

方法:动态规划

思路同 115. 不同的子序列,区别在于该题左右两边的字符串均可以进行删除操作

  • dp[i][j] 表示以 i-1 为结尾的单词 word1 和以 j-1 为结尾的单词 word2 达到相同所需的最小步数

  • 初始化

    • dp[i][0] 表示以 i-1 为结尾的单词 word1 和以 -1 为结尾的单词 word2 达到相同所需的最小步数,即为以 i-1 为结尾的单词 word1 和空字符串达到相同所需的最小步数,所以设置为 i
    • dp[0][j] 表示以 -1 为结尾的单词 word1 和以 j-1 为结尾的单词 word2 达到相同所需的最小步数,即为空字符串和以 j-1 为结尾的单词 word2 达到相同所需的最小步数,所以设置为 j
  • 外部循环表示对单词 word1 的循环,内部循环表示对单词 word2 的循环

    • 若两个单词的字符相同,即 word1[i-1] == word2[j-1],那么此时结尾的字符并不需要被删除,因此此时两个字符串达到相同所需的最小步数即为以 i-2 为结尾的 word1 和以 j-2 为结尾的 word2 达到相同所需的最小步数 dp[i-1][j-1]
    • 若两个单词的字符不同,即 word1[i-1] ≠ word2[j-1],那么此时结尾的字符需要被删除,删除的方式有三种:删除 word1[i-1],即 word2[j-1] 可以同 word1 中字符相匹配,那么此时 dp[i][j] 等于 word1[0, i-2] 和 word2[0, j-1] 达到相同所需的最小步数 dp[i-1][j] 加一;删除 word2[j-1],即 word1[i-1] 可以同 word2 中字符相匹配,那么此时 dp[i][j] 等于 word1[0, i-1] 和 word2[0, j-2] 达到相同所需的最小步数 dp[i][j-1] 加一;同时删除 word1[i-1] 和 word2[j-1],即两个字符均无法相匹配,那么此时 dp[i][j] 等于 word1[0, i-2] 和 word2[0, j-2] 达到相同所需的最小步数 dp[i-1][j-1] 加二
      因为求的是最小步数,那么应选择三种方式的最小值
class Solution(object):
    def minDistance(self, word1, word2):
        dp = [[0] * (len(word2)+1) for row in range(len(word1)+1)]
        for i in range(len(word1)+1):
            dp[i][0] = i
        for j in range(1, len(word2)+1):
            dp[0][j] = j
        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]+2)
        return dp[-1][-1]
参考

代码相关:https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html

相关文章

网友评论

      本文标题:LeetCode 583. 两个字符串的删除操作

      本文链接:https://www.haomeiwen.com/subject/inlqgrtx.html