编辑距离

编辑距离的状态如何定义？

• 问题: 求把 word1 改成 word2 的最少操作数, 允许插入、删除、替换 (72);
• 状态: dp[i][j] 为把 word1 前 i 个字符改成 word2 前 j 个字符的最少操作数;
• 对应字符: word1[i-1] 与 word2[j-1];
• 答案: dp[m][n];

三种操作分别对应哪个状态？

操作	含义	来源状态
添加	word2 多出一个字符, 从 dp[i-1][j] 补	dp[i-1][j] + 1
删除	word1 多出一个字符, 从 dp[i][j-1] 删	dp[i][j-1] + 1
替换	末位字符不同, 换成一致	dp[i-1][j-1] + 1

• 相同则无需操作: dp[i][j] = dp[i-1][j-1];

初始条件如何设置？

• 空串到空串: dp[0][0] = 0;
• 首行: word1 为空, 变成 word2 前 j 个字符需插入 j 次, dp[0][j] = j;
• 首列: word2 为空, 删除 word1 前 i 个字符需 i 次, dp[i][0] = i;

const minDistance = (word1, word2) => {
  const m = word1.length;
  const n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => 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 - 1][j], dp[i][j - 1]) + 1;
    }
  }
  return dp[m][n];
};

• 复杂度: 时间 O(mn), 空间 O(mn);