牛商网专注营销型网站建设,杭州富阳网站建设,南昌公司网站建设公司,自己做博客网站题目链接
给定两个单词 word1 和 word2 #xff0c;返回使得 word1 和 word2 **相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1#xff1a;
输入: word1 sea, word2 eat
输出: 2
解释: 第一步将 sea 变…题目链接
给定两个单词 word1 和 word2 返回使得 word1 和 word2 **相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1
输入: word1 sea, word2 eat
输出: 2
解释: 第一步将 sea 变为 ea 第二步将 eat 变为 ea
示例 2:
输入word1 leetcode, word2 etco
输出4
提示
1 word1.length, word2.length 500word1 和 word2 只包含小写英文字母 我们可以定义一个二维数组dp其中dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最小步数。
首先我们需要考虑边界情况当word1和word2的长度分别为零时它们已经相同了所以dp[0][0] 0。当word1为空字符串而word2不为空时则需要删除word2中的所有字符所以dp[0][j] j。同理当word2为空字符串而word1不为空时需要删除word1中的所有字符所以dp[i][0] i。
接下来我们考虑状态转移方程。假设我们要计算dp[i][j]即将word1的前i个字符转换为word2的前j个字符所需的最小步数。我们有以下几种情况 如果word1[i-1]等于word2[j-1]即当前字符相等那么不需要进行删除操作所以dp[i][j] dp[i-1][j-1]。 如果word1[i-1]和word2[j-1]不相等那么我们有两种选择 删除word1[i-1]字符然后将word1的前i-1个字符转换为word2的前j个字符所以dp[i][j] 1 dp[i-1][j]。删除word2[j-1]字符然后将word1的前i个字符转换为word2的前j-1个字符所以dp[i][j] 1 dp[i][j-1]。综上所述我们可以得到状态转移方程 if word1[i-1] word2[j-1]:dp[i][j] dp[i-1][j-1]
else:dp[i][j] 1 min(dp[i-1][j], dp[i][j-1])
最后我们可以通过填充dp数组来计算所需的最小步数。最终的结果即为dp[len(word1)][len(word2)]。
def minDistance(word1, word2):m, n len(word1), len(word2)dp [[0] * (n1) for _ in range(m1)] # 初始化dp数组# 初始化边界情况for i in range(m1):dp[i][0] ifor j in range(n1):dp[0][j] j# 计算dp数组for i in range(1, m1):for j in range(1, n1):if word1[i-1] word2[j-1]:dp[i][j] dp[i-1][j-1]else:dp[i][j] 1 min(dp[i-1][j], dp[i][j-1])return dp[m][n]
