LeetCode.72 - 编辑距离

• LeetCode - 72. 编辑距离

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

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

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

思路

1. 动态规划，dp[i][j] 维护 word1[:i] 与 word2[:j] 的最少操作次数
2. 初始化 dp[i][0] = i，dp[0][j] = j
3. word[i] === word2[j] 时，dp[i][j] = dp[i - 1][j - 1]
4. word[i] !== word2[j] 时，dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

var minDistance = function (word1, word2) {
  const dp = new Array(word1.length + 1).fill(null).map(() => new Array(word2.length + 1).fill(0))
  for (let i = 0; i <= word1.length; ++i) {
    dp[i][0] = i
  }
  for (let j = 0; j <= word2.length; ++j) {
    dp[0][j] = j
  }
  for (let i = 0; i < word1.length; ++i) {
    for (let j = 0; j < word2.length; ++j) {
      if (word1[i] === word2[j]) {
        dp[i + 1][j + 1] = dp[i][j]
      } else {
        dp[i + 1][j + 1] = Math.min(dp[i + 1][j], dp[i][j + 1], dp[i][j]) + 1
      }
    }
  }
  return dp[word1.length][word2.length]
}