题目描述

image.png

解题思路

  • dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
  • 递推公式
    • 当word1[i-1]==word2[j-1]：此时不进行操作,dp[i][j] = dp[i-1][j-1]
    • 不相等时
      • 删除（注意此时删除word2也就是添加word1，所以并不可以同时删除，题目要求把word1转化为word2）
        • 删除word1[i-1]
        • 删除word2[j-1]
      • 添加：注意添加操作和删除是一样的效果，一个添加就相当于另一个删除
      • 替换：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。
  • 初始化

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
那么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;

  • 遍历顺序

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

  • 举例推到dp数组

以示例1为例，输入：word1 = “horse”, word2 = “ros”为例，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 = 0; i <= word1.length(); i++) {
  5.         dp[i][0] = i;   // 此时word2是空字符串，word1需要全部删除才能匹配
  6.     }
  7.     for (int j = 0; j <= word2.length(); j++) {
  8.         dp[0][j] = j;   // 此时word1是空字符串，word2需要全部删除才能匹配
  9.     }
  11.     for (int i = 1; i <= word1.length(); i++) {
  12.         for (int j = 1; j <= word2.length(); j++) {
  13.             if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
  14.                 dp[i][j] = dp[i - 1][j - 1];    // 相同就不进行增删替换操作
  15.             } else {
  16.                 // 删除：
  17.                 //  删除word1的元素 dp[i - 1][j] + 1，删除word2的元素 dp[i][j - 1] + 1
  18.                 // 新增:
  19.                 //  新增和删除的操作次数一致，word1 = "ad" ，word2 = "a"，word1删除元素'd' 和 word2添加一个元素'd'，变成word1="a", word2="ad"， 最终的操作数是一样！
  20.                 // 替换:
  21.                 //  替换就是下标i-1和j-1前面位置的操作次数加上一，位置也就是i-2和j-2，对应dp[i - 1][j - 1] + 1
  22.                 // 三个操作取最小的操作
  23.                 dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
  24.             }
  25.         }
  26.     }
  28.     return dp[word1.length()][word2.length()];
  29. }