72.编辑距离.md

72.编辑距离

/*
 * @lc app=leetcode.cn id=72 lang=typescript
 *
 * [72] 编辑距离
 */

// @lc code=start
function minDistance(word1: string, word2: string): number {}
// @lc code=end

解法 1: 动态规划

• 时间复杂度:

  其中 m 为 word1 的长度,n 为 word2 的长度

• 空间复杂度:

1. 子问题: word1[0-i] 到 word2[0-j] 的最少操作数
2. 状态:
   • dp[i][j]: word1[0~i] 转换成 word2[0~j] 所需的最小操作数
3. DP 方程
   • word1[i]===word2[j]: dp[i][j]=dp[i-1][j-1]
   • word1[i]!==word2[j]: dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
4. 边界
   • 当与空字符进行操作时,则第 i 个字符的操作数就等于 i

function minDistance(word1: string, word2: string): number {
  const [m, n] = [word1.length, word2.length]
  const dp = [[0, ...new Array(n).fill(0).map((_, i) => i + 1)]]

  for (let i = 1; i <= m; i++) {
    dp[i] = [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]
}

解法 2: 优化空间

• 时间复杂度:

  其中 m 为 word1 的长度,n 为 word2 的长度

• 空间复杂度:

  n 为两个字符串中较小者的长度

function minDistance(word1: string, word2: string): number {
  const [m, n] = [word1.length, word2.length]
  if (m < n) return minDistance(word2, word1)

  const dp = new Array(word2.length + 1).fill(0).map((_, i) => i)

  for (let i = 1; i <= m; i++) {
    let pre = dp[0]
    dp[0] = i
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) [dp[j], pre] = [pre, dp[j]]
      else [dp[j], pre] = [Math.min(dp[j - 1], dp[j], pre) + 1, dp[j]]
    }
  }

  return dp[n]
}

Case

test.each([
  { input: { word1: 'horse', word2: 'ros' }, output: 3 },
  { input: { word1: 'intention', word2: 'execution' }, output: 5 },
  { input: { word1: '', word2: '' }, output: 0 },
  { input: { word1: 'sea', word2: 'eat' }, output: 2 },
  { input: { word1: '', word2: 'a' }, output: 1 },
])(`input: word1 = $input.word1, word2 = $input.word2`, ({ input: { word1, word2 }, output }) => {
  expect(minDistance(word1, word2)).toBe(output)
})