Skip to content

Latest commit

 

History

History
130 lines (87 loc) · 7.22 KB

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

File metadata and controls

130 lines (87 loc) · 7.22 KB

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

题目

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

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

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

示例1:

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

思考

看到题目的第一感觉是按照人的直觉做题,比如示例中 horseros 其中都有 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) 开始,就已经全部完成了 word1word2 的转换,如果要计算 dp(0),就只能删除 word1 的第 i 项,依此类推,这样无法模拟各种可能的操作。对第二中定义也类似。

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

动态规划

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

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

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

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

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

也许会有新手问,为什么没有考虑 i-2,ji-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)

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

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 的情况,因此对于 ij 都要提前计算一下为 -1 时的值,而当下标为 -1 时,等价于该字符串为空,那么空字符串如何转换为 word2,或 word1 如何转换为空字符串呢?只要执行对方下标 + 1 次的增或删就行了。

总结

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

讨论地址是:精读《算法 - 编辑距离》· Issue #501 · dt-fe/weekly

如果你想参与讨论,请 点击这里,每周都有新的主题,周末或周一发布。前端精读 - 帮你筛选靠谱的内容。

版权声明:自由转载-非商用-非衍生-保持署名(创意共享 3.0 许可证