题目描述

image.png

解题思路

DP1

此题和不同子序列的区别是两边都可以删除。

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

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

  • 递推公式
    • 当word1[i-1]==word2[j-1]时，此时就是上一个字符串，不用删除操作dp[i][j]=dp[i-1][j-1]
    • 不相等时
      • 删除word1[i-1]，操作次数dp[i - 1][j] + 1
      • 删除word2[j-1]，操作次数dp[i][j - 1] + 1
      • 两个都删除，操作次数dp[i - 1][j - 1] + 2，最终三个取最小
  • dp数组如何初始化

从递推公式中，可以看出来，dp[i][0] 和 dp[0][j]是一定要初始化的。
dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。

  • 确定遍历顺序

根据递推公式可得，从上到下，从左到右遍历。

  • 举例推导dp数组

以word1:”sea”，word2:”eat”为例，推导dp数组状态图如下：
image.png

  1. public int minDistance(String word1, String word2) {
  2.     // dp[i][j]表示以i-1为结尾的word1和j-1为结尾的word2，想要两个字符串相同所需要删除元素的最小次数是dp[i][j]
  3.     int[][] dp = new int[word1.length() + 1][word2.length() + 1];
  4.     for (int i = 1; i <= word2.length(); i++) {
  5.         dp[0][i] = i;   // word1为为空字符串，那么word2就需要删除相应的元素才能为空字符串
  6.     }
  8.     for (int i = 1; i <= word1.length(); i++) {
  9.         dp[i][0] = i;   // word2为为空字符串，那么word1就需要删除相应的元素才能为空字符串
  10.     }
  11.     dp[0][0] = 0;   // 都为空不需要删除
  13.     for (int i = 1; i <= word1.length(); i++) {
  14.         for (int j = 1; j <= word2.length(); j++) {
  15.             if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
  16.                 dp[i][j] = dp[i - 1][j - 1];    // 相等的话不需要删除
  17.             } else {
  18.                 //                        当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
  19.                 //                        当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：
  20.                 //                        情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
  21.                 //                        情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
  22.                 //                        情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
  23.                 //                        那最后当然是取最小值，所以当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});
  24.                 dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,Math.min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));
  25.             }
  26.         }
  27.     }
  29.     return dp[word1.length()][word2.length()];
  30. }

DP2

本题和动态规划：1143.最长公共子序列(opens new window)基本相同，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

  1. /**
  2.          * 只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数
  3.          *
  4.          * @param word1
  5.          * @param word2
  6.          * @return
  7.          */
  8. public int minDistance(String word1, String word2) {
  9.     int[][] dp = new int[word1.length() + 1][word2.length() + 1];
  10.     dp[0][0] = 0;   // 都为空字符串，相同公共子序列为0
  12.     for (int i = 1; i <= word1.length(); i++) {
  13.         for (int j = 1; j <= word2.length(); j++) {
  14.             if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
  15.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  16.             } else {
  17.                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
  18.             }
  19.         }
  20.     }
  22.     return word1.length() + word2.length() - dp[word1.length()][word2.length()] * 2;
  23. }