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

难度中等257收藏分享切换为英文接收动态反馈

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

示例：

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

提示：

1. 给定单词的长度不超过500。
2. 给定单词中的字符只含有小写字母。

动态规划 中等

转化为1143. 最长公共子序列

代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        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] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        lcs = dp[m][n]
        return m - lcs + n - lcs

当然也可以优化成一维空间

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        # dp = [[0] * (n + 1) for _ in range(m + 1)]
        curRow, lstRow = [0] * (n + 1), [0] * (n + 1)
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    curRow[j] = lstRow[j - 1] + 1
                else:
                    curRow[j] = max(lstRow[j], curRow[j - 1])
            lstRow, curRow = curRow, [0] * (n + 1)
        
        lcs = lstRow[n]
        return m - lcs + n - lcs