【算法练习Day47】两个字符串的删除操作&&编辑距离

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：练题
🎯长路漫漫浩浩，万事皆有期待

两个字符串的删除操作

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

这道题也是对于编辑距离的铺垫题目，是可以操作两个字符串的删除，使得两个字符串的字符完全相同，这道题可以用递推公式模拟删除，也可以使用求两个字符串的最大公共子序列的解题方法，求出最长的公共非连续子序列，然后再用两个字符串本身的长度减去这个公共子序列长度，也可以求出至少要删除几步。这里只分析第一种解题方法。

dp数组的含义：dp【i】【j】表示以i-1为下标的字符串1和以j-1为结尾的字符串2，要想使它们相等，所要删除的最小步数是多少。

递推公式：由于dp数值含义，当字符串1的i-1为结尾的下标元素，与字符串2以j-1为结尾的下标元素相等时，dp【i】【j】=dp【i-1】【j-1】。含义是当前元素相等，那么到达当前的位置需要删除的步数就和上一个位置的所需步数相等，因为此时元素相等，没有删除元素。

第二种情况就是两个对应元素不相等，这时又分为两种不同情况，即两元素不等的时候，删除第一个字符串的元素，或者是删除第二个字符串的元素，比较一下当前是哪一种删除的步数可以得到最小值。第一种就是删除字符串1的那个字符，那就是dp【i-1】【j】+1，dp数组的定义是i-1和j-1的下标的，所以此时j就代表前一个字符不变，然后略过字符串1这个字符，去向前找上一次的删除步数是多少，第二种情况是删除字符串2自然就是，dp【i】【j-1】+1，最后取最小值。

dp数组初始化：初始化一般是看递推公式决定的，当字符串1为空时候，字符串2需要删除当前字符个数的步数才能达到空字符串也就是需要删除j个。当字符串2为空也是同样的道理，字符串1需要删除i个。根据这一性质我们可以初始化第一行和第一列，也就是两个分别是空字符串情况，其他的部分统一初始化为0因为递推公式会全部覆盖。

遍历顺序：根据递推公式可知，从上到下，从左到右。

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));
        dp[0][0]=0;
        for(int i=1;i<=word1.size();i++)dp[i][0]=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,dp[i][j-1]+1);
            }
        }
        return dp[word1.size()][word2.size()];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

编辑距离

72. 编辑距离 - 力扣（LeetCode）

编辑距离是一道困难题，有了前面几期的铺垫，这道题也能更容易理解一些，这道题是求使两个字符串能变相等的最小操作数有几步，题目要求可以使任意一个字符串增加一个字符，或删除一个字符，或替换该指定位置的字符，看起来题目要求有一些复杂，但是实际上还是较容易理解的，主要是要弄懂递推公式的意义是什么。

dp数组的含义：dp数组的含义是到第一个字符串i-1的位置和第二个字符串j-1位置为止，所用最少的步数能使它们相等。

递推公式：我们来看如果两对应下标字符对应相等，那么就应该是当前的位置最少步数，等于上一次对应下标的最少步数。

if（word1【i-1】==word2【j-1】dp【i】【j】=dp【i-1】【j-1】

如果两对应下标字符不等，那么我们先来分析删除字符

根据往期的删除字符的操作，即是当两个字符确认已经不等时候，要么是不考虑字符1当前的字符而去考虑前一个位置，要么就是不考虑字符2的当前字符，去考虑它的前一个字符。然后取最小值。也就是dp【i-1】【j】和dp【i】【j-1】两者取最小值。那么增加字符怎么写呢？这是关键，实际上增加字符是和删除字符的递推公式是完全一样的。因为我们删除了字符串1的一个字符，不就是相当于增加了字符串2的一个字符吗？我们要增加的字符一定是我们所需要的字符，也就是字符串2里没有的但是字符串1里有的，反之同理，所以说它们的操作本质上是一样的。那么还剩下最后一种情况，就是交换两个字符串，word1替换word1【i-1】或者word2替换word2【j-1】才能使两字符串相等，回顾一下如果这两个字符相同的话，那么在dp数组应表现为dp【i】【j】=dp【i-1】【j-1】，所以当他们不同，而且此时又不是增删操作时候，我们替换其中一个字符所用的最少步数应该是dp【i-1】【j-1】+1。也就是说替换一个字符就可以让word1【i-1】和word2【j-1】相等。根据上面的推理，我们得出结论，递推公式就是他们三种情况取最小的方案。

dp数组的初始化：dp数组初始化与上一道题思路是相同的，当一个串是空串时，那么另一个串就需要删除全部字符，才能与之相等，按照这一思路来初始化。

遍历顺序：由递推公式可知，遍历顺序是从左到右，从上到下的。

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]+1,min(dp[i-1][j]+1,dp[i][j-1]+1));
                }
            }
            return dp[word1.size()][word2.size()];
        }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

重要的是要理清递推公式的思想，其他的部分和以往做的题没有什么太大区别，即使它是一道困难题。

总结：

今天我们完成了两个字符串的删除操作、编辑距离两道题，相关的思想需要多复习回顾。接下来，我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~