滨州市住房和城乡建设部网站,软件网站开发,设计师每天都上的网站,衡水做企业网站代码随想录算法训练营第56天|583. 两个字符串的删除操作#xff0c;72. 编辑距离 583. 两个字符串的删除操作72. 编辑距离 583. 两个字符串的删除操作
题目链接#xff1a;583. 两个字符串的删除操作#xff0c;难度#xff1a;中等 【实现代码】
class Solution {
publi… 代码随想录算法训练营第56天|583. 两个字符串的删除操作72. 编辑距离 583. 两个字符串的删除操作72. 编辑距离 583. 两个字符串的删除操作
题目链接583. 两个字符串的删除操作难度中等 【实现代码】
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size() 1, vectorint(word2.size() 1));for (int i 0; i word1.size(); i) {dp[i][0] i;}for (int j 0; j word2.size(); j) {dp[0][j] j;}for (int i 1; i word1.size(); i) {for (int j 1; j word2.size(); j) {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.back().back();}
};【解题思路】 动规五部曲 确定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]不相同的时候有三种情况 a) 情况一删word1[i - 1]最少操作次数为dp[i - 1][j] 1; b) 情况二删word2[j - 1]最少操作次数为dp[i][j - 1] 1; c) 情况三同时删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);dp数组如何初始化dp[i][0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。dp[0][j]的话同理确定遍历顺序遍历的时候一定是从上到下从左到右举例推导dp数组 72. 编辑距离
题目链接72. 编辑距离难度困难 【实现代码】
class Solution {
public:int minDistance(string word1, string word2) {vectorvectorint dp(word1.size() 1, vectorint(word2.size() 1));for (int i 0; i word1.size(); i) {dp[i][0] i;}for (int j 0; j word2.size(); j) {dp[0][j] j;}for (int i 1; i word1.size(); i) {for (int j 1; j word2.size(); j) {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], dp[i - 1][j - 1]}) 1;}}}return dp.back().back();}
};【解题思路】 动规五部曲 确定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]不相同的时候有三种情况 a)word1删除一个元素那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作即 dp[i][j] dp[i - 1][j] 1 b) 操作二word2删除一个元素那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。即 dp[i][j] dp[i][j - 1] 1; word2添加一个元素相当于word1删除一个元素例如 word1 “ad” word2 “a”word1删除元素’d’ 和 word2添加一个元素’d’变成word1“a”, word2“ad” 最终的操作数是一样 c) 只需要一次替换的操作就可以让 word1[i - 1] 和 word2[j - 1] 相同。所以 dp[i][j] dp[i - 1][j - 1] 1;dp数组如何初始化dp[i][0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。dp[0][j]的话同理确定遍历顺序遍历的时候一定是从上到下从左到右举例推导dp数组
