pre = 'abcde123'
now = '1abc123'

a前面插入了1, c后面删除了de

参考答案

思路：编辑距离

  • 动态规划求编辑距离
  • 倒着将变化输出。dp[i] === dp[i - 1] + 1
function compareStrings(pre, now) {
  const m = pre.length;
  const n = now.length;
  const dp = new Array(m + 1).fill().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 (pre[i - 1] === now[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;
      }
    }
  }
  let i = m;
  let j = n;
  let diff = "";
  while (i > 0 || j > 0) {
    if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {
      diff = `删除${pre[i - 1]}, ${diff}`;
      i--;
    } else if (j > 0 && dp[i][j] === dp[i][j - 1] + 1) {
      diff = `插入${now[j - 1]}, ${diff}`;
      j--;
    } else {
      i--;
      j--;
    }
  }
  return diff;
}
const pre = 'abcde123';
const now = '1abc123';
const diff = compareStrings(pre, now);
console.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] 的操作。