Day56 | 583. 两个字符串的删除操作 | 72. 编辑距离-Toy模板网

这篇具有很好参考价值的文章主要介绍了Day56 | 583. 两个字符串的删除操作 | 72. 编辑距离。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

注意点：

1.当word1[i - 1] 与 word2[j - 1]不相同的时候，

情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

因为dp[i][j-1]+1 = dp[i-1][j-1]+2，最后当然是取最小值min(dp[i-1][j]+1, dp[i][j-1]+1)

class Solution {
public:
    int minDistance(string word1, string word2) {
        // dp：i-1的word1和j-1的word2相同所需的最小步数
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1));
        // 初始化  当dp[0][0]的时候直接就是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, dp[i][j-1]+1, dp[i-1][j-1]+2);
    // 当word1[i-1] != word2[j-1]时，对i-1或者j-1取最小值即可，dp[i][j-1]+1 = dp[i-1][j-1]+2
                else dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1);
            }
        }
        return dp[word1.size()][word2.size()];


    }
};

72. 编辑距离

注意点：

min三个数的时候要加{}，如min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]})+1;

删除操作，word1删除dp[i-1][j]，word2删除dp[i][j-1]，所以是dp[i-1][j], dp[i][j-1]

3. 添加操作，word1删除和word2添加操作数是一样的，word1 = ab, word2 = a, 删除word1中的b;word2添加后是ab 所以是dp[i-1][j], dp[i][j-1]

4. 替换后才能到达if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1]，所以在dp[i-1][j-1]的基础上加1文章来源地址https://www.toymoban.com/news/detail-472394.html

class Solution {
public:
    int minDistance(string word1, string word2) {
        // dp[i][j]：以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最少操作数为dp[i][j]
        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];
                // 这是删除操作，word1删除dp[i-1][j]，word2删除dp[i][j-1]
                // 添加操作，word1删除和word2添加操作数是一样的，word1 = ab, word2 = a, 删除word1中的b;word2添加后是ab 
                // 替换后才能到达if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1]，所以在dp[i-1][j-1]的基础上加1
                else dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]})+1;
            }
        }
        
        return dp[word1.size()][word2.size()];
    }
};

到了这里，关于Day56 | 583. 两个字符串的删除操作 | 72. 编辑距离的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！