算法学习 | day48/60 两个字符串的删除操作/编辑距离

一、题目打卡

        1.1 两个字符串的删除操作

        题目链接：. - 力扣（LeetCode）

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 题目可以理解为，找到最大的长度的相同子序列
        vectorint>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
 
        int max_son = 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]);
                max_son = max(max_son, dp[i][j]);
            }
        }
        // cout  << max_son << endl;
        return word1.size() + word2.size() - 2 * max_son;
    }
};

         题目要求最少需要多少步骤的删减让两个字符串相等，因为只涉及到删除，没有添加和更换字符，所以其实可以统计出最大的相同子序列，再用两者的size进行计算就可以了。

        1.2 编辑距离

        题目链接：. - 力扣（LeetCode）

class Solution {
public:
    int minDistance(string word1, string word2) {
        vectorint>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
 
        for(int i = 0 ; i <= word1.size();i++) dp[i][0] = i;
        for(int i = 0 ; i <= word2.size();i++) dp[0][i] = i;
 
 
        for(int i = 1 ; i < word1.size() + 1; i++){
            for(int j = 1 ; j < word2.size() + 1; 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 - 1][j], dp[i][j - 1]}) + 1;
            }
        }
        // for(int i = 0; i <= word1.size();i++){
        //     for(int j = 0 ; j <= word2.size();j++){
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << endl;
        // }
 
        return dp[word1.size()][word2.size()];
 
    }
};

        这个题目在很多的方面刷新了我的固有认知，首先是我之前以为在声明dp数组的时候，如果进行了 size + 1 的操作，其实是为了不进行初始化就可以直接推理了，但是其实不然，主要还是要考虑dp数组的定义，比如这个题目dp数组被定义为：以 i - 1 为结尾的字符串 word1，和以下标 j - 1 为结尾的字符串 word2，最近的编辑距离为dp[i][j]，所以如果是d[0][i]和d[i][0]的话，其实是有定义在的，也就是从另一个字符串，要删除多少轮才能两者相等，所以这个题目也是需要初始化的。

        思考了一下，其实这样是为了初始化更简单，因为如果不这样的话，初始化的过程需要分别进行计算和考虑。

        然后这个题目的状态转移的理解，其实也是分相等和不相等两种情况：

if (word1[i - 1] == word2[j - 1])
    不操作
if (word1[i - 1] != word2[j - 1])
    增
    删
    换

        这里的不操作，其实就是因为当前这个字符就可以不用修改了，只需要修改两个字符之前的部分，也就是只需要继承 dp[i-1][j-1]。

        而不相等，需要分三种情况进行处理：

        每一种情况其实都是额外进行了一步操作就可以转化为目标的字符串（从0到j）了，所以转移的方式，就应该在这三个里面取最小的操作数，然后进行加 1 的操作。