精读《算法题 - 编辑距离》

今天我们看一道 leetcode hard 难度题目：编辑距离。

题目

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

思考

看到题目的第一感觉是按照人的直觉做题，比如示例中 horse 与 ros 其中都有 os，那么最短编辑距离肯定要维持 os 相对位置不变。但该方法可能更适合大模型用直觉做题，而不是和用代码编写，背后有太多无法固化的逻辑。

看来只能用动态规划暴力解决，但如何定义变量呢？

如果我们仅用一个变量，只有两种定义方法：

• dp(i) 返回 word1 下标为 i 时最短编辑距离。
• dp(i) 返回 word2 下标为 i 时最短编辑距离。

对第一种定义，我们的目标是计算出 dp(word1.length-1)，其中 dp(-1) 即 word1 从空字符串转换为 word2 需要的编剧距离显然是 word2.length，即把 word2 依次添加到 word1。但严重的问题是 dp(i) 与 dp(i-1) 的关系没有意义，因为从 dp(-1) 开始，就已经全部完成了 word1 到 word2 的转换，如果要计算 dp(0)，就只能删除 word1 的第 i 项，依此类推，这样无法模拟各种可能的操作。对第二中定义也类似。

这种想法的根本问题是，将 word1 到 word2 转换时，要么一次从空字符串转换为完整的 word2，要么从完整的 word1 转换为空字符串，这背后无法体现一个一个字符的考虑，所以必须用两个变量，分别定义 i、j 下标才行。

动态规划

有了上面的思考，动态规划的定义就清楚了：

定义 i 为 word1 下标，j 为 word2 下标，dp(i,j) 返回 word1 下标为 i，且 word2 下标为 j 时最短编辑距离。

让我们再审视一下 dp(i,j) 的含义：除了返回最短编辑距离外，正因为我们知道了最短编辑距离，所以无论操作步骤、过程如何，都可以假设我们只要做了若干步操作，下标分别截止到 i、j 的 word1、word2 内容就完全相同了！这真是太优美了，一下就把复杂的问题简单化了，我们只要考虑当前步骤，也要清晰的知道之前步骤的状态代表什么含义。

接下来考虑状态转移，由于没有任何操作限制，我们必须把所有可能的转移都考虑进去，包括：

• i-1,j
• i,j-1
• i-1,j-1

也许会有新手问，为什么没有考虑 i-2,j、i-3,j-1 等等情况？这是因为函数是递归调用的，i-2,j 等价于 i-1,j + i-1,j，为了简化代码复杂度，只考虑一层转换的心智负担最低，又能通过递归实现所有操作可能性。

此时老手可能会问，那 i-1,j-1 不就等价于 i-1,j + i,j-1 吗？这么列出来不是重复了吗？说的很对，我们要意识到这一点，但同时还要进一步意识到每一步操作都有成本，本题还支持替换字符串操作，该操作可以一步实现 i-1,j + i,j-1 两步行为，考虑它可以减少操作步骤，肯定会影响到最终答案。

接着我们要思考状态转移方程是什么，仔细阅读下面的思考过程：

对于 i-1,j，因为 i-1,j 经过 dp(i-1,j) 次数的操作后，word1[0,i-1] 与 word2[0,j] 已经完全相同了，我们的目的就是让两边字符串相同，所以 word1[i] 这个多出来的字符串需要毫不留情的删除，删除需要一步，因此 dp(i,j) = dp(i-1,j) + 1，该步是删除。

对于 i,j-1，因为 i,j-1 经过 dp(i,j-1) 次数的操作后，word1[0,i] 与 word2[0,j-1] 已经完全相同了，我们的目的就是让两边字符串相同，所以 word2[j] 这个字符是截止到 word1[0,i] 需要新增上去的，因此 dp(i,j) = dp(i,j-1) + 1，该步是新增。

对于 i-1,j-1，因为 i-1,j-1 经过 dp(i-1,j-1) 次数的操作后，word1[0,i-1] 与 word2[0,j-1] 已经完全相同了，我们的目的就是让两边字符串相同，所以对于 word1[i] 到 word2[j] 来说，如果它俩字符相同，则不需要操作，如果不相同，执行一次替换操作即可，因此在 word1[i] 与 word2[j] 不同是，dp(i,j) = dp(i,j-1) + 1，该步是替换。

对 i-1,j-1 的思考让我们意识到需要优先考虑 word1[i] 与 word2[j] 相同的情况，这种情况只要看前一个字符的结果就行，不需要产生额外的操作，因此转移方程是：dp(i,j) = dp(i-1,j-1)。

最后再考虑一下边界情况，当 word1 与 word2 任意为空时，只要执行非空字符串长度次数的增或删就行了。

function minDistance(word1: string, word2: string): number {
  // 任意一个字符串为空时，执行非空字符串长度次数的增或删
  if(word1 === '' || word2 === '') {
    return word1.length + word2.length
  }

  const dp = new Map()

  function getDp(i: number, j: number) {
    return dp.get(`${i},${j}`)
  }

  function calcDp(i: number, j: number) {
    // 兼容下边界情况
    if (i === 0 && j === 0) {
      return word1[0] === word2[0] ? 0 : 1
    }

    if (word1[i] === word2[j]) {
      return getDp(i-1, j-1)
    }

    return Math.min(
      // i-1, j: 删除第 i 项
      getDp(i-1, j) + 1,
      // i, j-1: 增加第 i 项
      getDp(i, j-1) + 1,
      // i-1, j-1: 替换第 i 项
      getDp(i-1, j-1) + 1
    )
  }

  for (let i = 0; i < word1.length; i++) {
    dp.set(`${i},-1`, i + 1)
  }

  for (let j = 0; j < word2.length; j++) {
    dp.set(`-1,${j}`, j + 1)
  }

  for (let i = 0; i < word1.length; i++) {
    for (let j = 0; j < word2.length; j++) {
      dp.set(`${i},${j}`, calcDp(i, j))
    }  
  }

  return getDp(word1.length-1, word2.length-1)
};

其中花了我一些时间的地方在于边界情况处理，比如当 i=0 时，dp(i-1,j) 就出现了 i=-1 的情况，因此对于 i、j 都要提前计算一下为 -1 时的值，而当下标为 -1 时，等价于该字符串为空，那么空字符串如何转换为 word2，或 word1 如何转换为空字符串呢？只要执行对方下标 + 1 次的增或删就行了。

总结

当意识到该题没有捷径时，就要考虑动态规划方案了，而动态规划第一难点在于定义参数，第二难点在于写状态转移方程，而只要定义对了参数，状态转移方程也就呼之欲出了，因此最难的一步就是定义参数，对这道题参数定义还有疑问的小伙伴可以回到 思考 章节重新阅读一下。

本文由哈喽比特于6月以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/Vue4YLwehE9Sl0vcIilHGA