Day56 动态规划part16 583. 两个字符串的删除操作 72. 编辑距离

本文主要是介绍Day56 动态规划part16 583. 两个字符串的删除操作 72. 编辑距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Day56 动态规划part16 583. 两个字符串的删除操作 72. 编辑距离

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

方法一：动态规划

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0)); //以i-1为结尾word1和以j-1为结尾word2，是两者相同最小步数dp[i][j]for(int i = 0; i<=word1.size();i++) dp[i][0] = i;   //初始化dp[i][0]以i-1为结尾word1,转化成空字符串需要i步for(int j = 1; 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,min(dp[i][j-1]+1,dp[i-1][j-1]+2));}}return dp[word1.size()][word2.size()];}
};

方法二：先求最长连续子序列长度，计算删除数量

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0)); 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;else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}return word1.size()+word2.size()-2*dp[word1.size()][word2.size()]; //word1长度+word2长度-最长连续子序列长度*2 = 需要删除的元素个数}
};

72. 编辑距离

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));for(int i = 0; i<=word1.size();i++) dp[i][0] = i;   //初始化dp[i][0]以i-1为结尾word1,转化成空字符串需要i步，583.两个字符串的删除操作相同初始化流程for(int j = 1; 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]+1,min(dp[i-1][j]+1,dp[i][j-1]+1)); //dp[i-1][j]+1:删掉word1,dp[i][j-1]+1:删掉word2,逆向可以从删除情况考虑到增加情况}   //dp[i-1][j-1]+1：替换情况}return dp[word1.size()][word2.size()];}
};