问题

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

示例：

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

思路

这次是两个字符串可以相互删了，这种题目也知道用动态规划的思路来解，动规五部曲，分析如下：

  • 确定dp数组以及下标的含义

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

  • 确定递推公式

    • 当word1[i - 1] 与 word2[j - 1]相同的时候

    • 当word1[i - 1] 与 word2[j - 1]不相同的时候

    • 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];

    • 当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：
      • 情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
      • 情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
      • 情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
      • 那最后当然是取最小值，所以当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});

  • dp数组如何初始化

    • 从递推公式中，可以看出来，dp[i][0] 和 dp[0][j]是一定要初始化的
    • dp[i][0]：word2为空字符串，以i-1为结尾的字符串word2要删除多少个元素，才能和word1相同呢，很明显dp[i][0] = i，dp[0][j]的话同理 ```java 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;

  2. - 确定遍历顺序
  3.    - 从递推公式`dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j], dp[i][j - 1]) + 1)`和`dp[i][j] = dp[i - 1][j - 1]`可以看出`dp[i][j]`都是根据左上方、正上方、正左方推出来的
  5. - 举例推导dp数组
  6.    - 以`word1:"sea"`，`word2:"eat"`为例，推导`dp`数组状态图如下：![640 (1).webp](https://cdn.nlark.com/yuque/0/2021/webp/463136/1625973011255-eae2e4df-2283-437f-ada2-76936047ba4f.webp#clientId=u826e1541-0ac5-4&from=ui&id=ue7fc891c&margin=%5Bobject%20Object%5D&name=640%20%281%29.webp&originHeight=684&originWidth=846&originalType=binary&ratio=1&size=19240&status=done&style=none&taskId=u8a544154-ef09-4e79-8cbc-1a617398ea4)
  7. ```java
  8. class Solution {
  9.     public int minDistance(String word1, String word2) {
  10.         int[][] dp = new int[word1.length() + 1][word2.length() + 1];
  11.         for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;
  12.         for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;
  14.         for (int i = 1; i <= word1.length(); i++) {
  15.             for (int j = 1; j <= word2.length(); j++) {
  16.                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
  17.                     dp[i][j] = dp[i - 1][j - 1];
  18.                 }else{
  19.                     dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,
  20.                                         Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
  21.                 }
  22.             }
  23.         }
  24.         return dp[word1.length()][word2.length()];
  25.     }
  26. }