本文主要是介绍代码随想录算法训练营第55天|583.两个字符串的删除操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
583.两个字符串的删除操作
1.最长公共子序列法
这道题我看弹幕说“秒了”，怎么大家都那么厉害，然后看到“最长公共子序列”，好家伙，又是它，还是得转换一下思路，求最少得删除多少个元素可不就是先求最长的公共子序列，然后两个字符串分别减去最长公共子序列的长度吗，所以代码
是和最长公共子序列是差不多的。
2.计算删除元素法
这个类似于不同的子序列那道题，其实就是求删除元素的最小值，所以设置dp[i][j]为word1的第i个位置(从1开始计算),word2的第j个位置(从1开始计算)时删除元素的最小值，假如说word1[i-1]==word2[j-1]，那么这就不用删除元素了，所以dp[i][j]=dp[i-1][j-1]，假如说word1[i-1]!=word2[j-1]，那么这时候就要删除元素了，可以删除word1[i-1]也可以删除word2[j-1]，也可以两个都删除，就要看哪种方法使得删除的元素小了，所以dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2)。
https://leetcode.cn/problems/delete-operation-for-two-strings/
class Solution {
public:int minDistance(string word1, string word2) {// vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1));// 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()];vector<vector<int>>dp(word1.size()+1,vector<int>(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,min(dp[i][j-1]+1,dp[i-1][j-1]+2));}}}return dp[word1.size()][word2.size()];}
};72.编辑距离
这道题细看代码其实和上一道题的第二种方法很像，只是要把题目的意思换个角度思考，dp[i][j]依旧是word1的第i个位置（从1开始计算）word2的第j个位置(从1开始计算)的最小的删除元素的个数，假如说word1[i-1]==word2[j-1]，那么dp[i][j]=dp[i-1][j-1],假如说不等于，那么对于现在这个位置即i,j有三种方法，分别是增，删，改，如果是增的话，就是dp[i][j-1]+1，相当于在第j个位置前面增加元素，如果是删的话，就是dp[i-1][j]+1，相当于删除第i个位置，如果是改的话，就是dp[i-1][j-1]+1。
https://leetcode.cn/problems/edit-distance/
class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>>dp(word1.size()+1,vector<int>(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,min(dp[i][j-1]+1,dp[i-1][j-1]+1));}}}return dp[word1.size()][word2.size()];}
};这篇关于代码随想录算法训练营第55天|583.两个字符串的删除操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
