算法训练营 Day 55 | 583. 两个字符串的删除操作 ● 72. 编辑距离

[KoEkko]

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

function minDistance(word1: string, word2: string) {
  const m = word1.length;
  const n = word2.length;
  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[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[m][n];
}

72. 编辑距离

dp[i][j]表示 以i-1为结尾的字符串word1和以j-1为结尾的字符串word2，最短编辑距离是dp[i][j];

以i-1和j-1结尾是为了初始化方便；

确定递推公式有两种情况

1. word1[i - 1] === word2[j - 1]
   不操作
2. word1[i - 1] !== word2[j - 1];
   增、删、改

if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];
if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？

操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i - 1][j] + 1;

操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。
即 dp[i][j] = dp[i][j - 1] + 1;

这里其实我们只需要考虑删除操作就行了， 因为删除和添加操作其实编辑次数都是一样的，我们可以删除多的元素达到相同，也可以添加少的字符达到相同，最后编辑操作的次数都是一样的。也就是逆向操作
eg: s1="ab",s2="a", 可以s1删除"b"，也可以s2添加"b"，结果都是一样的；

改的话，就是在相同结尾的基础上增加一步操作就可以了；
dp[i][j] = dp[i-1][j-1] + 1;

最后在这几个操作中取最小值即可；
3. dp数组如何初始化
再回顾一下dp[i][j]的定义：

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;

function minDistance(word1: string, word2: string) {
  const dp: number[][] = new Array(word1.length + 1)
    .fill(0)
    .map(() => new Array(word2.length + 1).fill(0));
  for (let i = 0; i <= word1.length; i++) {
    dp[i][0] = i;
  }
  for (let j = 0; j <= word2.length; j++) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= word1.length; i++) {
    for (let j = 1; j <= word2.length; j++) {
      if (word1[i - 1] === word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
      else {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      }
    }
  }
  return dp[word1.length][word2.length];
}