思路：编辑距离

• 动态规划求编辑距离
• 倒着将变化输出。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        // 末尾字符相同，不需要任何操作
15        dp[i][j] = dp[i - 1][j - 1];
16      } else {
17        // 本题只允许「插入」「删除」，所以不取 dp[i-1][j-1] + 1（那是「替换」）
18        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
19      }
20    }
21  }
22  // 回溯：从右下角走回左上角，注意要先判「末尾字符相同」这一支
23  let i = m;
24  let j = n;
25  const diff = [];
26  while (i > 0 || j > 0) {
27    if (i > 0 && j > 0 && pre[i - 1] === now[j - 1]) {
28      // 匹配，无需记录
29      i--;
30      j--;
31    } else if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {
32      diff.unshift(`删除${pre[i - 1]}`);
33      i--;
34    } else {
35      diff.unshift(`插入${now[j - 1]}`);
36      j--;
37    }
38  }
39  return diff.join(', ');
40}
41const pre = 'abcde123';
42const now = '1abc123';
43const diff = compareStrings(pre, now);
44console.log(diff); // 输出：插入1, 删除d, 删除e
45
46console.log(compareStrings('abcde123', '11ade123')); // 输出：插入1, 插入1, 删除b, 删除c

解释：

dp[i][j] 表示把 pre 的前缀 pre[0...i-1] 变成 now 的前缀 now[0...j-1] 所需的最少操作数。本题只要求输出「插入」和「删除」两类操作，因此状态转移只考虑这两种：

1. 删除：把 pre[0...i-2] 变成 now[0...j-1]，再删掉 pre[i-1]，即 dp[i-1][j] + 1；
2. 插入：把 pre[0...i-1] 变成 now[0...j-2]，再插入 now[j-1]，即 dp[i][j-1] + 1；
3. 若 pre[i-1] === now[j-1]，末尾字符相同不需要操作，即 dp[i-1][j-1]。

（如果还要识别「替换」，转移里就再取 dp[i-1][j-1] + 1，回溯时也必须单独判断这一支，否则替换会被误判成匹配。）

回溯时同样要先判断「末尾字符是否相同」这一支：如果跳过这一步，当 dp[i][j] 恰好等于 dp[i-1][j] + 1 时，一次「匹配」会被误判成「删除」，一路走到最后什么操作都输出不出来。例如 compareStrings('abcde123', '11ade123')，旧写法返回空串，正确结果是 插入1, 插入1, 删除b, 删除c。