力扣● 583. 两个字符串的删除操作 ● 72. 编辑距离 ● 编辑距离总结篇

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

注意审题：

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

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

删除最少的字符使两者相同，说明留下来的就是最大公共子序列。不要求连续，所以可以使用● 1143.最长公共子序列 来做，最长公共子序列之外的字母都要删除，所以返回 (n1+n2-2*dp[n1][n2]) 即可。

这是间接求法，直接求：

1.dp数组含义。

dp[i][j]：以word1[i-1]为结尾的字符串，和以word2[j-1]位结尾的字符串，想要达到相等，所需要删除元素的最少次数为dp[i][j]。

2.递推公式。

如果相等：删除次数要最少，那么相等的话就不能删除，得留着，所以dp[i][j]=dp[i-1][j-1];

如果不等：2个字符串没有谁长谁短的前提，所以应该有3种情况。

①可能删掉word1[i-1]，那么dp[i][j]代表的子序列和dp[i-1][j]代表的子序列删除的字母，就多了一个：word1[i-1]，所以dp[i][j]=dp[i-1][j]+1；

②可能删掉word2[j-1]，同样，dp[i][j]=dp[i][j-1]+1；

③都删除。都删除的话，dp[i][j]代表的子序列和dp[i-1][j-1]代表的子序列删除的字母，就多了2个：word1[i-1]和word2[j-1]，所以是dp[i][j]=dp[i-1][j-1]+2；这其实也是满足情况①和情况②的，删掉2个，和dp[i-1][j]相比多删了一个word2[j-1]，和dp[i][j-1]相比多删了一个word1[i-1]。所以情况①/情况②就把③包含了。所以只取①和②的最小删除数量，即Min值就是对的。

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

3.初始化。

dp[i][0]。i>0时，word1[i-1]：非空串；word2[0,-1]：空串。所以应该删除word1的前i个达到相等。

dp[0][j]。同样应该删除word2的前j个达到相等。

dp[0][0]。不用删除，=0。

4.遍历顺序。

5.打印。

代码如下：

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

● 72. 编辑距离

1.dp数组含义。

dp[i][j]：数组1[0,i-1]中操作（插删换）dp[i][j]次，得到的序列是数组2[0,j-1]。注意这个操作过程是可逆的，2[0,j-1]中操作（删插换）dp[i][j]次，得到的序列是1[0,i-1]。

所以每一步操作，既可以对数组1操作，也可以对数组2操作。我觉得变换一下题目解法也没有变：请返回操作后使word1和word2相同的最大操作数。

举例：“horse”变成“ros”：

horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

因为，对数组1 的 插入 等同于对数组2 的删除，删除同理，那么：

ros -> rose (插入 'e')；horse-> rorse(将 'h' 替换为 'r')；rose -> rorse(插入 'r')。

即中间每步可以选择对1操作，也可以对2操作。可见操作后可以得到很多种相同字符串（horse、rorse、rose或ros），但是过程中数组1和数组2操作的次数之和是固定的，即编辑距离是固定的。

2.递推公式。

（1）不相等的话，这3个操作都有可能发生，那么是肯定要加上1（做一个操作）。

①替换：

可以1[i-1]替换成2[j-1]，也可以2[j-1]替换成1[i-1]。改了之后，得到的2个子数组最后元素相同，所以应该是在dp[i-1][j-1]的基础上替换了1或2的一个元素，所以+1。

即dp[i][j]=dp[i-1][j-1]+1。

②可以删除：

删除1[i-1]达到相同，说明[0,i-2]中操作之后，就能得到2[0,j-1]了，所以是在这个基础（dp[i-1][j]）之上加一个删除操作即可，即dp[i][j]=dp[i-1][j]+1。

也可以删除2[j-1]达到相同，那么同理，dp[i][j]=dp[i][j-1]+1。

③可以插入：

插入1[i-1]达到相同，代表着删除2[i-1]达到相同，上面说了只是操作不同但次数相同，所以在1或2插入的情况都可以用删除表示，所以1[i-1]后面插入的情况下dp[i][j]==dp[i][j-1]+1。2[j-1]后面插入的情况下dp[i][j]=dp[i-1][j]+1。上面都包含了。

所以：dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;

（2）相等：和上题同样是求最少操作数，所以相等的话不操作，即dp[i][j]=dp[i-1][j-1]。

3.初始化。

回忆dp的含义：

dp[i][0]=i。以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。

dp[0][j]=j。同理。

4.遍历顺序。

从上到下，从左到右。

5.打印。

代码如下：

class Solution {
public:int minDistance(string word1, string word2) {int n1=word1.size();int n2=word2.size();vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));for(int j=0;j<=n2;++j)dp[0][j]=j;//删除for(int i=0;i<=n1;++i)dp[i][0]=i;//插入for(int i=1;i<=n1;++i){for(int j=1;j<=n2;++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[n1][n2];}
};

● 编辑距离总结篇   

做多了总结一下：都是在dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]的基础上得到dp[i][j]，要得到这个递推公式，就是得清楚，什么情况下，对A[i-1]（B[j-1]）做什么操作，比如上面● 72. 编辑距离，不相同的话，可能对A[i-1]和B[j-1]这一对，修改其中一个就行，所以是在dp[i-1][j-1]基础上+1……

总结一下3个编辑距离前导题：

判断子序列

判断s是不是t的子序列。根据最长公共子序列来做，dp[i][j]不要求si-1、t[j-1]结尾。

2个元素相等的时候。dp[i][j]=dp[i-1][j-1]+1;

不相等。因为序列1一定比序列2短，不相等的话dp[i][j-1]一定大于dp[i-1][j]，所以dp[i][j]=dp[i][j-1]；

不同的子序列

统计序列s在序列t中出现的个数。

2个元素相同。s[i-1]有可能匹配t[j-1]以及t[j-1]之前的与之相等的元素。

所以dp[i][j]=dp[i-1][j-1]+dp[i-1][j-1]；

不相同。s[i-1]只可能匹配t[j-1]之前的，所以dp[i][j]=dp[i-1][j]。

两个字符串的删除操作

统计序列s和序列t，删除最少几个元素变成一样。

相同。dp[i][j]=dp[i-1][j-1]

不同。省略了删除2个dp[i-1][j-1]+2。dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1)；