代码随想录算法训练营第四十八天|583. 两个字符串的删除操作，72. 编辑距离

作者：小蓝xlanll | 2024-03-14 11:52:18

踩

系列文章目录

文章目录

系列文章目录
583. 两个字符串的删除操作
72. 编辑距离

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

题目链接： 583. 两个字符串的删除操作
题目内容： 给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。
视频讲解： 动态规划之子序列，还是为了编辑距离做铺垫 | LeetCode：583.两个字符串的删除操作

动态规划问题的五步曲：

确定dp数组（dp table）以及下标的含义：dp[i][j]表示以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
确定递推公式：
- 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
- 当word1[i - 1] 与 word2[j - 1]不相同的时候，dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
dp数组如何初始化：dp[i][0] = i，dp[0][j]=j
确定遍历顺序：从左到右遍历，从上到下遍历
举例推导dp数组

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(word1)+1):
            dp[i][0]=i
        for j in range(len(word2)+1):
            dp[0][j]=j
        for 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,dp[i-1][j-1]+2)
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

72. 编辑距离

题目链接： 72. 编辑距离
题目内容： 给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符，删除一个字符，替换一个字符
视频讲解： 动态规划终极绝杀！ LeetCode：72.编辑距离

动态规划问题的五步曲：

确定dp数组（dp table）以及下标的含义：以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2的最少操作次数就是 dp[i][j]
确定递推公式：
- 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
- 当word1[i - 1] 与 word2[j - 1]不相同的时候，dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]})+1;
dp数组如何初始化：dp[i][0] = i，dp[0][j]=j
确定遍历顺序：从左到右遍历，从上到下遍历
举例推导dp数组

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(word1)+1):
            dp[i][0] = i
        for j in range(len(word2)+1):
            dp[0][j] = j
        for 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-1][j], dp[i][j-1]) + 1
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/234162