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

第九章 动态规划part16

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

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

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

思路：其实与前面求两个字符串的最长公共子序列完全一致，只是换了一个问法。

可见前一篇blog中1143.最长公共子序列思路代码随想录算法训练营第五十三天|1143. 最长公共子序列、1035. 不相交的线、53. 最大子数组和-CSDN博客

dp[i][j]含义：以下标i-1为结尾的word1字符串与以j-1下标为结尾的word2字符串的最长公共子序列长度。

不直接使用i/j比较方便，否则初始化比较麻烦。

class Solution {
public:
    int minDistance(string word1, string word2) {
        vectorint>> 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]);
            }
        }
        return word1.size()+word2.size()-2*dp[word1.size()][word2.size()];
    }
};

 也可以直接定义dp[i][j]使得以下标i-1为结尾的word1字符串与以j-1下标为结尾的word2字符串相同所需的最小步数。

72. 编辑距离

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

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

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

思路：前面几道题都是这一类关于两个字符串子序列问题，基本的思路都是从dp[i-1][j-1]、dp[i][j-1]、dp[i-1][j]三个状态分析推导出dp[i][j]。所以这道题解的也是误打误撞，纯粹推导中找到规律。写完看了题解才能理解出状态推导的真正含义。

重点是word1[i-1]!=word2[j-1]时可能的三种操作，对应了增、删、改。

①word1增加word2[j-1]元素，dp[i][j-1]+1;

②word1删除i-1元素，dp[i-1][j]+1;

③word1[i-1]元素替换为word2[j-1]，dp[i-1][j-1]+1。

从三种操作中寻找修改的最小步数，即实现状态转移。

初始化也需要注意，dp[0][j]=j可以理解为空字符串转化为j-1为结尾的word2字符串所需要操作的最小步数，dp[i][0]=i可以理解为以i-1为结尾的word1字符串转换为空字符串所需的最小步数，就能对应上了。

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