583. 两个字符串的删除操作
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例：
输入: "sea", "eat" 输出: 2 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
提示：
- 给定单词的长度不超过500。
- 给定单词中的字符只含有小写字母。
法1 动态规划·
思路
典型的双序列类型题目。按照套路
题解
class Solution: def minDistance(self, word1: str, word2: str) -> int: dp = [[0] * (len(word2)+1) for _ in range(len(word1)+1)] for i in range(len(dp)): dp[i][0] = i for j in range(len(dp[0])): dp[0][j] = j for i in range(1, len(dp)): for j in range(1, len(dp[0])): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1 return dp[-1][-1]