代码随想录算法训练营第56天 | 583.两个字符串的删除操作, 72.编辑距离, 编辑距离总结篇

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

代码随想录链接

题目

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

给定两个单词, 为使两个单词相同, 每一步可以删除任意一个字符串中的一个字符, 求至少需要多少步可以使得两个字符串相同.

题目分析

动态规划五部曲:

• 确定dp数组及下标的含义

  dp[i][j]表示以i-1结尾的字符串word1和以j-1结尾的字符串word2想要达到相等要删除的元素次数.

• 递推公式

  分为两种情况:

  • word1[i] == word2[j]

    此时, dp[i][j] = dp[i - 1][j - 1]

  • word1[i] != word2[j]

    这个时候, 可以选择删除word1[i - 1]处的字符, 也可以选择删除word2[j - 1]处的字符, 亦或是同时删除word1[i - 1]和word2[j - 1]处的字符

    dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2))

• dp数组的初始化

  dp[i][0]和dp[0][j]是一定要初始化的, 而根据dp数组及下标的意义, 所有dp[i][0]都应该被赋值为i, dp[0][j]同理.

• 遍历顺序

  外层for循环遍历word1中字符, 内层for循环遍历word2中字符.

题解

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

72.编辑距离

代码随想录链接

题目

LeetCode-72.编辑距离

给定两个单词, 规分别插入, 删除, 替换一个字符为1步, 求将第一个字符串转化为第二个字符串需要几步.

题目分析

动态规划五部曲:

• 确定dp数组及下标的含义

  dp[i][j]代表以下标i-1结尾的字符串word1, 和以下标j-1为结尾的字符串word2, 最近的编辑距离.

• 递推公式

  分为两种情况:

  • word1[i - 1] == word2[j - 1]

    此时, 当前位置的编辑距离和两个字符串在上一个字符比较时的结果一样, dp[i][j] = dp[i - 1][j - 1]

  • word1[i - 1] != word2[j - 1]

    可以进行的操作有, 删除word1[i-1], 删除word2[j-1], 替换word1[i-1]为word2[j-1]

    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1

• dp数组的初始化

  和上一题一样, 需要对dp[i][0]和dp[0][j]进行初始化, 且初始化方式相同.

• 遍历顺序

  外层for循环遍历word1中字符, 内层for循环遍历word2中字符.

题解

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.back().back();
    }
};

编辑距离总结篇

代码随想录链接