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

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

示例 1：

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

输入：word1 = “leetcode”, word2 = “etco”
输出：4

方法一：最长公共子序列
给定两个字符串 word1和 word2，分别删除若干字符之后使得两个字符串相同，则剩下的字符为两个字符串的公共子序列。为了使删除操作的次数最少，剩下的字符应尽可能多。当剩下的字符为两个字符串的最长公共子序列时，删除操作的次数最少。因此，可以计算两个字符串的最长公共子序列的长度，然后分别计算两个字符串的长度和最长公共子序列的长度之差，即为两个字符串分别需要删除的字符数，两个字符串各自需要删除的字符数之和即为最少的删除操作的总次数。最长公共子序列的长度，记为lcs，则最少删除操作次数为 m−lcs+n−lcs。

方法二：动态规划
也可以直接使用动态规划计算最少删除操作次数，不需要计算最长公共子序列的长度。假设字符串word1和word2的长度分别为m 和 n，创建dp, dp[i][j] 表示使word1前面i个字符word[0:i] 和 word2前面j个字符word2[0:j] 相同的最少删除操作次数。
动态规划的边界情况如下：
当 i=0 时，空字符串和任何字符串要变成相同，只有将另一个字符串的字符全部删除，因此对任意 0≤j≤n，有 dp[0][j]=j；
当 j=0 时，同理可得，对任意 0≤i≤m，有 dp[i][0]=i。

dp[i][j] 的计算：

当 word1[i−1]=word2[j−1]时，将这两个相同的字符称为公共字符，考虑使
word1[0:i−1] 和 word2[0:j−1] 相同的最少删除操作次数，增加一个公共字符之后，最少删除操作次数不变，因此 dp[i][j]=dp[i−1][j−1]

当 word1[i−1] !=word2[j−1] 时，考虑以下两项：
使word1[0:i−1] 和 word2[0:j] 相同的最少删除操作次数，加上删除 word1[i−1] 的 1 次操作；使 word1[0:i] 和 word2[0:j-1]相同的最少删除操作次数，加上删除 word2[j−1] 的1 次操作。因此 dp[i][j]=min(dp[i−1][j]+1,dp[i][j−1]+1)

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