手机在线建站,建设银行官网首页网站南山片区,生态网站模板,教育网站制作价格文档讲解#xff1a;代码随想录 视频讲解#xff1a;代码随想录B站账号 状态#xff1a;看了视频题解和文章解析后做出来了 583. 两个字符串的删除操作
class Solution:def minDistance(self, word1: str, word2: str) - int:dp [[0] * (len(word2)1) for _ in range(… 文档讲解代码随想录 视频讲解代码随想录B站账号 状态看了视频题解和文章解析后做出来了 583. 两个字符串的删除操作
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] ifor j in range(len(word2)1):dp[0][j] jfor 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] 2, dp[i-1][j] 1, dp[i][j-1] 1)return dp[-1][-1] 时间复杂度O(n^2) 空间复杂度O(n)
1. 确定dp数组的含义
dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。
2. 确定递推公式
当word1[i - 1] 与 word2[j - 1]相同的时候dp[i][j] dp[i - 1][j - 1];
当word1[i - 1] 与 word2[j - 1]不相同的时候有三种情况
情况一删word1[i - 1]最少操作次数为dp[i - 1][j] 1
情况二删word2[j - 1]最少操作次数为dp[i][j - 1] 1
情况三同时删word1[i - 1]和word2[j - 1]操作的最少次数为dp[i - 1][j - 1] 2
所以当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[i][j - 1] 1 dp[i - 1][j - 1] 2所以递推公式可简化为dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1);
3. dp数组初始化
从递推公式中可以看出来dp[i][0] 和 dp[0][j]是一定要初始化的。
dp[i][0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。
4. 确定遍历顺序
从递推公式 dp[i][j] min(dp[i - 1][j - 1] 2, min(dp[i - 1][j], dp[i][j - 1]) 1); 和dp[i][j] dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。
所以遍历的时候一定是从上到下从左到右这样保证dp[i][j]可以根据之前计算出来的数值进行计算。
5. 举例 72. 编辑距离
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] ifor j in range(len(word2)1):dp[0][j] jfor 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]) 1return dp[-1][-1] 时间复杂度O(n^2) 空间复杂度O(n)
1. 确定dp数组的含义
dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。
2. 确定递推公式
详情见卡哥文档
3. dp数组初始化
从递推公式中可以看出来dp[i][0] 和 dp[0][j]是一定要初始化的。
dp[i][0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。
4. 确定遍历顺序
从递推公式 dp[i][j] min(dp[i - 1][j - 1] 2, min(dp[i - 1][j], dp[i][j - 1]) 1); 和dp[i][j] dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。
所以遍历的时候一定是从上到下从左到右这样保证dp[i][j]可以根据之前计算出来的数值进行计算。
5. 举例
