代码随想录训练营第五十六天583. 两个字符串的删除操作72. 编辑距离

本文主要是介绍代码随想录训练营第五十六天583. 两个字符串的删除操作72. 编辑距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目链接 583. 两个字符串的删除操作 - 力扣（LeetCode）

讲解链接 代码随想录 (programmercarl.com)

 对于字符串的删除操作，在确定好了dp数组的含义：dp[i][j]表示到达word1下标i-1，word2下标j-1相等时所需要的最小步数，这样对于dp数组的初始化可以根据内在含义来进行，对于dp[i][0]表示要把前i个元素全部删除，j也同样：

        for(int i=0;i<=word1.size();i++)dp[i][0]=i;for(int j=0;j<=word2.size();j++)dp[0][j]=j;

再来分析递归函数，每一次移动都有两种可能：相等或者不等；

当相等时，dp[i][j]=dp[i-1][j-1]（不用考虑这两个元素了）；

当不相等时，dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][i-1]+2)（删除word1、删除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];else{dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+2));}}}

72. 编辑距离 

题目链接 72. 编辑距离 - 力扣（LeetCode）

讲解链接 代码随想录 (programmercarl.com)

 定义dp数组dp[i]为使word1[i-1]之前的数组完全转化为word[j]所需要的最小步数，此时初始化dp数组，dp[i][0]=i,dp[0][j]=j,最后就是可能出现的情况，倘若当前i-1元素与j-1元素相等，此时dp[i][j]=dp[i-1][j-1],若是不相等则有三种可能：需要增加：dp[i][j]=dp[i][j-1]+1;需要删除：dp[i][j]=dp[i-1][j]+1;需要替换dp[i][j]=dp[i-1][j-1]+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];else{dp[i][j]=min({dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1});}}}

最后的元素就是所需要的最小步数

这篇关于代码随想录训练营第五十六天583. 两个字符串的删除操作72. 编辑距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---