[72] 编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

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

插入一个字符

删除一个字符

替换一个字符

示例 1:

输入：word1 = "horse", word2 = "ros"

输出：3

解释：

horse -> rorse （将 'h' 替换为 'r')

rorse -> rose （删除 'r')

rose -> ros （删除 'e')

示例 2:

输入：word1 = "intention", word2 = "execution"

输出：5

解释：

intention -> inention （删除 't')

inention -> enention （将 'i' 替换为 'e')

enention -> exention （将 'n' 替换为 'x')

exention -> exection （将 'n' 替换为 'c')

exection -> execution （插入 'u')

这道题与 [583] 两个字符串的删除操作 的题型十分相似，都是 diff 两字符串的问题。只是这道题的可操作范围从只能删除变成了允许增删改。

设原问题为 word1.slice(0, i) 转变为 word2.slice(0, j)。

涉及到双字符串匹配的动态规划问题永远是两个字符串中字符的比较，并且结果也只分为两类，相等和不相等。

若相等，则表示这两个字符匹配，不需要做任何操作，子问题直接变为 word1.slice(0, i-1) 转化为 word2.slice(0, j - 1)。即：dp[i, j] = dp[i - 1, j - 1]

若不相等，需要对字符进行操作，step + 1。这里对字符串有三种操作，分别是：

1. 删除，子问题即 word1.slice(0, i - 1) 转变为 word2.slice(0, j)。即：dp[i, j] = dp[i - 1, j] + 1

2. 替换，子问题即 word1.slice(0, i - 1) 转变为 word2.slice(0, j - 1)。即：dp[i, j] = dp[i - 1, j - 1] + 1

3. 添加，子问题即 word1.slice(0, i) 转变为 word2.slice(0, j - 1)。即：dp[i, j] = dp[i, j - 1] + 1

function minDistance(word1: string, word2: string): number {
  const len1 = word1.length;
  const len2 = word2.length;
  const dp = Array(len1 + 1)
    .fill(0)
    .map(x => Array(len2 + 1).fill(0));

  for (let j = 0; j <= len2; j++) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= len1; i++) {
    dp[i][0] = i;
    for (let j = 1; j <= len2; 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], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      }
    }
  }
  return dp[len1][len2];
}