代码随想录打卡—day56—【编辑距离】— 9.2 编辑距离系列

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

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

【注意点1】感觉和下面这题很像。就是一模一样，return变一下就是。

1143. 最长公共子序列

【注意点2】注意这题和day55的最后一题的区别，本题求的是最大长度，那题求的是组合方式。

AC代码：

class Solution {
public:int dp[510][510]; // word1的前i-1的字符串 与 word2的前i-1的字符串的最长公共子序列长度/*if(word1[i-1] == word2[j-1])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i][j-1],dp[i-1][j]);dp[0][0] = 0dp[i][0] = 0dp[0][j] = 0i++ j++模拟——*/int minDistance(string word1, string word2) {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] + 1;elsedp[i][j] = max(dp[i][j-1],dp[i-1][j]);}}return word1.size() + word2.size() - 2*dp[word1.size()][word2.size()];}
};

2 72. 编辑距离

72. 编辑距离

状态转移方程难推导。学习题解的，详见注释

AC代码：

class Solution {
public:int dp[510][510]; // word1的前i-1个的子串 转换成 word2的前j-1个的子串最小操作数/*if(word1[i-1] == word2[j-1]){dp[i][j] = dp[i-1][j-1];  //不用操作}else{//【1】 插入按照题解的说法 一个子串删除最后一个元素 等价于 另一个子串增加最后一个元素所以省去// 【2】 删除删掉word1[i-1]dp[i][j] = dp[i-1][j] + 1;删掉word2[j-1]dp[i][j] = dp[i][j-1] + 1;// 【3】 替换dp[i][j] = dp[i-1][j-1] + 1;}初始化：dp[0][0] = 0;dp[0][j] = j;dp[i][0] = i;顺序：i++ j++模拟：*/int minDistance(string word1, string word2) {for(int j = 0; j <= word2.size();j++)dp[0][j] = j;for(int i = 0; i <= word1.size();i++)dp[i][0] = i;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];  //不用操作elsedp[i][j] = min(dp[i-1][j],min(dp[i][j-1] , dp[i-1][j-1])) + 1;return dp[word1.size()][word2.size()];}
};

编辑距离系列总结

go to