583.两个字符串的删除操作 72.编辑距离

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

力扣题目链接(opens new window)

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

• 输入: “sea”, “eat”
• 输出: 2
• 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

思路

思路：动态规划
动态规划五部曲
1.定义dp数组以及下标含义
定义二维dp数组。dp[i][j]表示以字符word1[i]为结尾字符串和以字符word2 [j]为结尾字符串中，相同所需的最小步数
2。定义递推公式
情况一：word1[i] == word2 [j]
dp[i][j] = dp[i-1][j-1]
情况二：word1[i] ！= word2 [j]
dp[i][j] = Math.min(dp[i-1][j] + 1,dp[i][j-1] + 1);
3.初始化dp数组
考虑二维数组第一行和第一列如何初始化
第一行
第一个元素
if (word1.charAt(0) != word2.charAt(0)) {
    dp[0][0] = 2;
}
剩余元素
如果word1.charAt(i) == word2.charAt(0)，删除字符步数为i
如果word1.charAt(i) != word2.charAt(0)，【删除字符步数】跟【dp[0][0]】也就是word1.charAt(i) == word2.charAt(0)是否相等有关
1.相等。那么删除字符步数为dp[i][0] = i。举例如下 word1:abc word2:a.
dp[0][0] = 0.dp[1][0]表示删除ab等于a的步数，很显然为1，也就是i
可以得出dp[i][0] = i
2.不相等。那么删除字符步骤相比dp[i-1][0]应增加1.举例如下 word1:abc word2:t
dp[0][0] = 2.dp[1][0]表示删除ab等于t的步数，很显然为3，也就是dp[0][0] +1
可以得出dp[1][0] = dp[0][0] +1.即 dp[i][0] = dp[i - 1][0] + 1;
for (int i = 1; i < word1.length(); i++) {
    if (word1.charAt(i) == word2.charAt(0)) {
          dp[i][0] = i;
    } else {
         if (dp[0][0] == 0) {
            dp[i][0] = i;
         } else {
             dp[i][0] = dp[i - 1][0] + 1;
          }
    }
   }

第一列 同理
4.遍历顺序
有递推公式可知
从小到大遍历即可
5.举例推导dp数组
时间复杂度O(N^2)
空间复杂度O(N^2)

代码如下

public static void main(String args[]) {
    minDistance("sea", "ate");
}

public static int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null)// 边界条件处理
        return 0;
    if (word1.equals("") && !word2.equals(""))
        return word2.length();
    if ((!word1.equals("") && word2.equals("")))
        return word1.length();

    int[][] dp = new int[word1.length()][word2.length()];// 定义Dp数组以及初始化
    if (word1.charAt(0) != word2.charAt(0)) {
        dp[0][0] = 2;
    }
    for (int i = 1; i < word1.length(); i++) {
        if (word1.charAt(i) == word2.charAt(0)) {
            dp[i][0] = i;
        } else {
            if (dp[0][0] == 0) {
                dp[i][0] = i;
            } else {
                dp[i][0] = dp[i - 1][0] + 1;
            }
        }
    }
    for (int j = 1; j < word2.length(); j++) {
        if (word2.charAt(j) == word1.charAt(0)) {
            dp[0][j] = j;
        } else {
            if (dp[0][0] == 0) {
                dp[0][j] = j;
            } else {
                dp[0][j] = dp[0][j - 1] + 1;
            }
        }
    }

    for (int i = 1; i < word1.length(); i++) {
        for (int j = 1; j < word2.length(); j++) {
            if (word1.charAt(i) == word2.charAt(j)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            }
        }
    }
    return dp[word1.length() - 1][word2.length() - 1];

}

问题

问题1
本题目在推导dp公式时出现了错误
错误推导方式
情况二：word1[i] ！= word2 [j]
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]);
正确方式
忘记给步数加一了
dp[i][j] = Math.min(dp[i-1][j] + 1,dp[i][j-1] + 1);

问题2
初始化错误,初始化有点复杂
错误方式
没考虑到word1.charAt(i) != word2.charAt(0)时
【删除字符步数dp[i][0]】跟【dp[0][0]】有关

优化

本题目属于编辑距离类题目。只有删除操作，对word1和word2都有删除操作
二刷时采用另一种定义dp数组的方式、
dp[i][j]表示以word1[i-1]和word2[i-1]为结尾字符串中，使得 word1 和 word2 相同所需的最小步数
采用这种定义dp数组方式，可简化初始化dp数组流程
从递推公式中，可以看出来，dp[i][0] 和 dp[0][j]是一定要初始化的。
dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。
dp[0][j]的话同理

代码如下

public static int minDistance(String word1, String word2) {

    if (word1 == null || word2 == null)
        return 0;
    int[][] dp = new int[word1.length() + 1][word2.length() + 1];// 定义Dp数组以及初始化
    for (int i = 0; i <= word1.length(); i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= word2.length(); j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= word1.length(); i++) {
        for (int j = 1; j <= word2.length(); 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] + 1, dp[i][j - 1] + 1);
            }
        }
    }
    return dp[word1.length()][word2.length()];

}

72.编辑距离

力扣题目链接(opens new window)

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

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

• 插入一个字符
• 删除一个字符
• 替换一个字符
• 示例 1：
• 输入：word1 = “horse”, word2 = “ros”
• 输出：3
• 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)
• 示例 2：
• 输入：word1 = “intention”, word2 = “execution”
• 输出：5
• 解释： intention -> inention (删除 ‘t’) inention -> enention (将 ‘i’ 替换为 ‘e’) enention -> exention (将 ‘n’ 替换为 ‘x’) exention -> exection (将 ‘n’ 替换为 ‘c’) exection -> execution (插入 ‘u’)

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

思路

思路：动态规划
动态规划五部曲
1.定义dp数组以及下标含义
定义二维dp数组。dp[i][j]表示以字符word1[i-1]为结尾字符串和以字符word2 [j-1]为结尾字符串中，word1 转换成 word2 所使用的最少操作数 。
2.定义递推公式
word1[i-1] == word2 [j-1].dp[i][j] = dp[i-1][j-1]
word1[i-1] != word2 [j-1].对word1有增删改三种操作
word1删除操作 dp[i][j] = dp[i-1][j] + 1；
word1增加操作 dp[i][j] = dp[i + 1][j] + 1 = dp[i][j - 1] + 1；
word1修改操作 dp[i][j] = dp[i - 1][j - 1] + 1；
这里解释下word1增加操作递推公式怎么推导
当word1字符串尾部新增元素后，长度由i 变为 i + 1.那么dp[i][j] = dp[i + 1][j] + 1.但如果这么写的话，dp[i][j]就要先得到dp[i+1]的值才能推导出来
很显然和删除修改操作的dp公式存在冲突，这两个公式都是先得到dp[i - 1]的值后推导dp[i][j]。需要把dp[i + 1][j] 转换成跟 i-1有关的dp公式
word1添加一个元素，相当于word2删除一个元素，例如 word1 = "a" ，word2 = "ad"，word1添加元素'd' 和 word2删除一个元素'd'，变成word1="ad", word2="a"， 最终的操作数是一样！
所以word1增加操作 dp[i][j] = dp[i + 1][j] + 1 = dp[i][j - 1] + 1；
3.初始化dp数组
dp[i][0] 和 dp[0][j] 表示什么呢？
dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。
那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;
同理dp[0][j] = j;
4.遍历顺序
有递推公式可知
从小到大遍历即可
5.举例推导dp数组

代码如下

// 时间复杂度O(N^2)
// 空间复杂度O(N^2)
public int minDistance(String word1, String word2) {
    int[][] dp = new int[word1.length() + 1][word2.length() + 1];
    for (int i = 0; i <= word1.length(); i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= word2.length(); j++) {
        dp[0][j] = j;
    }


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

}