代码随想录训练营day56, 两个字符串的删除操作, 编辑字符

两个字符串的删除操作

动态规划1

1. 数组含义: 以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数

2. 递推公式:

   1. 当两个不相等(有三种情况)

      1. 删word[i-1], 操作次数为dp[i-1][j] + 1
      2. 删word[j-1], 操作次数为dp[i][j-1] + 1
      3. 同时删两个, 操作次数为dp[i-1][j-1] + 2 (dp[i-1][j-1] + 1等于上面either, 可忽略)

      (最后当然是取最小值)

3. 初始化: 当一个字符串是空的时, 需要几步才能变成相同的呢, 答案是i或者j

class Solution {
    public int minDistance(String word1, String word2) {
        //动规一, 通过取删除操作的最小值
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 2];
        //初始化, 都是i
				//这里是<=, 因为要让数组正好等于string长度
        for(int i = 0; i <= len1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= len2; j++){
            dp[0][j] = j;
        }
        //开始遍历
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                //如果相等的话又不用操作
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //不相等, 要么删i要么删j, 最小值
                    dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }
            }
        }
        return dp[len1][len2];
    }
}

动态规划2:

本题基础上和LC1143(最长公共子序列)是有点相似的, 只需要算出总共相同的字母长度, 然后全部的减去这个值就行了

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        //这个版本的话先求最长公共子序列, 初始值必然是0
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    //如果相等长度就加一
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    //否则分别退一步,看哪个大
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        //最后算出来的是长度, 所以两个加起来减去长度*2
        return len1 + len2 - dp[len1][len2]*2;
    }
}

编辑字符

给你两个word, 请计算出将word1转换成word2所使用的最小操作数(上一题只需要删除, 这里可以进行插入, 删除, 和替换)

仍然还是经典五部曲:

1. 数组定义: 以i-1和j-1为结尾的数据,最近编辑距离为dp[i][j]
2. 递推公式: 有四种操作: 不操作,增, 删, 改
   1. 如果word相等, 说明不用编辑, 那么就是dp[i-1][j-1]
   2. 如果不相等, 此时就要编辑栏
      1. 删除: word1或者word2删除一个元素, 次数加一: dp[i][j-1]+1/dp[i-1][j]+1
      2. 增加: 其实可以发现, 增加一个元素就是相当于另一个word减少一个元素
      3. 替换: 可以理解为两个都退一步, dp[i-1][j-1] + 1
3. 初始化: 这里和上一题一样 ,默认为i

class Solution {
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 0; i <= len1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= len2; j++){
            dp[0][j] = j;
        }
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    //相等则不做任何操作
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //不相等则做, 删除和替换的操作
                    dp[i][j] = Math.min(Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1),
                    dp[i-1][j-1] + 1);
                }
 
            }
        }
        return dp[len1][len2];
    }
}