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

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

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

题目链接：583. 两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

文章讲解/视频讲解：https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html

思路与实现

相当于寻找单词word1和单词word2中最长公共子序列，然后根据最长公共子序列的长度，计算最小步数。用动态规划来处理，设置一个二维dp数组，其中dp[i][j]代表0 ~ i - 1中的word1与0 ~ j - 1中的word2最长公共子序列的长度。

dp数组的递推式为：

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]);

需要将dp[0][j]和dp[i][0]初始化，根据定义，dp[0][j] = dp[i][0] = 0。

代码如下：

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]);}}int longest = dp[word1.size()][word2.size()];return word1.size() + word2.size() - 2 * longest;}
};

72. 编辑距离

题目链接：72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

文章讲解/视频讲解：https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html

思路与实现

这道题是之前的综合。设置一个二维dp数组，其中dp[i][j]表示0 ~ i - 1的word1与0 ~ j - 1的word2的最短编辑距离。题干中说了，对word1可以进行插入、删除、替换操作，其中对word1插入一个字符，等价于对word2删除一个字符。于是dp数组的递推式的主干为：

if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else{// 第一种操作，删除word1[i - 1]// 第二种操作，删除word2[j - 1]// 第三种操作，替换word1[i - 1]
}

其中删除word1[i - 1]时，dp[i][j] = dp[i - 1][j] + 1 ，删除word2[j - 1]时，dp[i][j] = dp[i][j - 1] + 1，替换word1[i - 1]时，dp[i][j] = dp[i - 1][j - 1] + 1，dp[i][j]应当取这三种操作的最小值。所以dp数组的递推式为：

if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;

然后就是要对dp数组初始化，即初始化dp[i][0]和dp[0][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;

代码如下：

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;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 - 1][j], dp[i][j - 1])) + 1;}}return dp[word1.size()][word2.size()];}
};