583-delete-operation-for-two-strings.md

583. Delete Operation for Two Strings - 两个字符串的删除操作

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

示例 1:

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

说明:

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

---

题目标签：String

题目链接：LeetCode / LeetCode中国

题解

两个单词的长度减去两倍的LCS即可。

LCS是很经典的问题，务必熟知！

LCS: 最长公共子序列

Language	Runtime	Memory
python3	584 ms	N/A

class Solution:
    def CLS(self, s1, s2):
        dp = [[0] * (len(s2)+1) for _ in range(len(s1)+1)]
        for i in range(1, len(s1)+1):
            for j in range(1, len(s2)+1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = 1 + dp[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]

    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        return len(word1) + len(word2) - 2 * self.CLS(word1, word2)