代码随想录|583. 两个字符串的删除操作，72. 编辑距离（有进一步理解到)

583. 两个字符串的删除操作（理解困难）

1.dp含义

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

2.dp递推公式

• 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j]=dp[i-1][j-1]
• 当word1[i - 1] 与 word2[j - 1]不相同的时候,有三种情况：1.删word1[i-1],最少操作次数为dp[i-1][j]+1;  2.删word[j-1]，最少操作次数为dp[i][j-1]+1;  3.同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2，
  • 注意点，这里dp[i - 1][j - 1] + 2= dp[i][j - 1] + 1  ，因为要做的是同时删除word1[i-1]和word2[j-1],dp[i][j-1]本来就不考虑word2[j-1]了，那么我在删除word1[i-1]是不是就能达到两个元素都删除的效果了，即dp[i - 1][j - 1] + 2= dp[i][j - 1] + 1
• 所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

3.dp初始化

从递推公式中，可以看出来，dp[i][0] 和 dp[0][j]是一定要初始化的。

dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。

4.确定遍历顺序，从前往后

5.推导dp

代码实现

class Solution {
    public int minDistance(String word1, String word2) {
        int m=word1.length();
        int n=word2.length();
        int[][] dp=new int[m+1][n+1];
        //dp初始化
        for(int i=0;i<=m;i++){dp[i][0]=i;}//表示以下标为i-1的word1和空字符串相等所需要的最少删除步数
        for(int j=0;j<=n;j++){dp[0][j]=j;}//表示以下标为j-1的word2和空字符串相等所需要的最少删除步数
 
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }
                else{
                    dp[i][j]=Math.min(dp[i][j-1]+1,dp[i-1][j]+1);
 
                }
            }
        }
        return dp[m][n];
 
    }
}

72. 编辑距离（有进一步理解到)

1.dp含义

截至到word1的下标为i-1位置和word2的下标为j-1位置使得二者单词变得相等需要进行的最少操作数

2.dp递推公式

如果word1[i-1]==word2[j-1],根据我们dp含义可以知道不用进行操作，dp[i][j]=dp[i-1][j-1]

如果word1[i-1]!=word2[j-1],我们有删除，插入，替换三种操作,但我们可以发现，如果我们有单词 A 和单词 B：

• 对单词A删除一个字符和对单词B插入一个字符是等价的，如A=“dog",B="doge",我们既可以在单词A末尾添加字母e，也可以删除单词B的末尾字母e
• 同理，对单词B删除一个字符和对单词A插入一个字符也是等价的
• 对单词A替换一个和对单词B替换一个也是等价的

所以在原来我们有六种操作基础上即删A,删B,增A,增B,替A,替B就变成本质只有3种操作，即：

删A删B(增A我觉得意思不好理解所以换成删)替A：dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1,其实dp[i-1][j]对应删A操作,dp[i][j-1]对应删B操作,dp[i-1][j-1]对应替换操作

3.dp初始化

dp[0][0]表示两个空字符串相等时候需要的最少步数，所以dp[0][0]=0

dp[i][0]表示截至下标为i-1的word1和空字符串word2相等所需要的最少步数所以d[i][0]=i

dp[0][j]表示空字符串和截至下标为j-1的word2相等所需要的最少步数即dp[0][j]=j

4.dp递推顺序

从前往后遍历

5.dp推导

代码实现

class Solution {
    public int minDistance(String word1, String word2) {
        //dp含义：截至到word1的下标为i-1位置和word2的下标为j-1位置使得二者单词变得相等需要进行的最少操作数
        int m=word1.length();
        int n=word2.length();
        int[][] dp=new int[m+1][n+1];  
        //初始化
        for(int i=0;i<=m;i++){dp[i][0]=i;}
        for(int j=0;j<=n;j++){dp[0][j]=j;}
        //
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){//不做任何操作
                    dp[i][j]=dp[i-1][j-1];
                }
                else{
                    dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
                }
                
            }
        }
        return dp[m][n];
    }
}