思路：编辑距离

• 动态规划求编辑距离
• 倒着将变化输出。dp[i] === dp[i - 1] + 1

复制
1function compareStrings(pre, now) {
2  const m = pre.length;
3  const n = now.length;
4  const dp = new Array(m + 1).fill().map(() => new Array(n + 1).fill(0));
5  for (let i = 0; i <= m; i++) {
6    dp[i][0] = i;
7  }
8  for (let j = 0; j <= n; j++) {
9    dp[0][j] = j;
10  }
11  for (let i = 1; i <= m; i++) {
12    for (let j = 1; j <= n; j++) {
13      if (pre[i - 1] === now[j - 1]) {
14        dp[i][j] = dp[i - 1][j - 1];
15      } else {
16        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
17      }
18    }
19  }
20  let i = m;
21  let j = n;
22  let diff = "";
23  while (i > 0 || j > 0) {
24    if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {
25      diff = `删除${pre[i - 1]}, ${diff}`;
26      i--;
27    } else if (j > 0 && dp[i][j] === dp[i][j - 1] + 1) {
28      diff = `插入${now[j - 1]}, ${diff}`;
29      j--;
30    } else {
31      i--;
32      j--;
33    }
34  }
35  return diff;
36}
37const pre = 'abcde123';
38const now = '1abc123';
39const diff = compareStrings(pre, now);
40console.log(diff); // 输出：插入1, 删除d, 删除e

解释：

我们将一个字符串转换成另一个字符串的操作分为三种：插入、删除、替换。在这个函数中，我们将删除操作定义为从 pre 字符串中删除一个字符，使得 pre 的前缀变为 now 的前缀。因此，在 dp 数组中，dp[i][j] 表示 pre 的前缀 pre[0...i-1] 变为 now 的前缀 now[0...j-1] 所需的最小操作次数。如果我们想要将 pre 的前缀 pre[0...i-1] 变为 now 的前缀 now[0...j-1]，可以有三种操作方式：

1. 插入一个字符：我们可以在 pre 的前缀 pre[0...i-1] 的末尾插入一个字符 now[j-1]，这样就将 pre 的前缀变为 now 的前缀。此时，dp[i][j] 的值应该为 dp[i][j-1] + 1。
2. 删除一个字符：我们可以将 pre 的前缀 pre[0...i-2] 变为 now 的前缀 now[0...j-1]，然后再删除字符 pre[i-1]，这样也能将 pre 的前缀变为 now 的前缀。此时，dp[i][j] 的值应该为 dp[i-1][j] + 1。
3. 替换一个字符：我们可以将 pre 的前缀 pre[0...i-2] 变为 now 的前缀 now[0...j-2]，然后再将字符 pre[i-1] 替换为字符 now[j-1]，这样也能将 pre 的前缀变为 now 的前缀。此时，dp[i][j] 的值应该为 dp[i-1][j-1] + 1。 在这个函数中，我们根据 dp 数组的值，逆推出从 pre 转换成 now 的具体操作。如果 dp[i][j] 的值是由 dp[i-1][j] 转移而来，那么说明我们需要删除字符 pre[i-1]，以使得 pre 的前缀变为 now 的前缀。因此，我们在返回字符串中加入 删除pre[i-1] 的操作。