72. Edit Distance

Leetcode link

题目简介

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */

题目给我们两个字符串 word1 与 word2，要求我们判断从 word1 变成 word2 最少需要多少次操作

操作的种类：

1. 替换字符 replace
2. 新增字符 insert
3. 删除字符 delete

解题思路

我们先尝试简化这个问题：假设 word1 与 word2 都只有一个字符

此时有两种情况：

1. word1 === word2：此时不需要任何操作即符合要求
2. word1 !== word2：此时我们需要一个 replace 操作

如果扩展成各有两个字符呢？假设 word1 = 'ab' ，word2 = 'cd'

我们可以画出如下表格：

我们重点看右下角的四个格子，其中：

1. a->c 符合我们上述第二种情况，需要一个 replace 操作

2. a->cd 在 a->c 的基础上我们需要额外的 insert 操作

3. ab->c 在 a->c 的基础上我们需要额外的 delete 操作

4. ab->cd 这种情况我们需要判断要基于哪一个状态进行操作，有三种选项：

   1. 选择 a->c 此时我们需要一个额外的 replace（replace b with d）
   2. 选择 a->cd 此时我们需要一个额外的 delete 操作（delete b）
   3. 选择 ab->c 此时我们需要一个额外的 insert 操作（insert c）

   要使得操作数最少，我们需要找出原来操作最少的操作，于是我们选中 a->c

综上，我们得到了状态转移方程（我们假设 dp[i][j] 代表 word1[0...i-1] 转变为 word2[0...j-1] 需要的最少操作数）

• 如果 word[i-1] === word2[j-1] ：dp[i][j] = dp[i-1][j-1]
• 否则：dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1

边界情况发生在第一行与第一列，所以我们给 dp 多一行一列给默认值

Javascript

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    const len1 = word1.length
    const len2 = word2.length
    const dp = Array.from({ length: len1 + 1 }, _ => new Array(len2 + 1).fill(0))

    for (let row = 0; row <= len1; row++) {
        dp[row][0] = row
    }
    for (let col = 0; col <= len2; col++) {
        dp[0][col] = col
    }

    for (let row = 1; row <= len1; row++) {
        for (let col = 1; col <= len2; col++) {
            if(word1[row - 1] === word2[col - 1]) {
                dp[row][col] = dp[row - 1][col - 1]
            } else {
                dp[row][col] = Math.min(dp[row - 1][col - 1], dp[row - 1][col], dp[row][col - 1]) + 1
            }
        }
    }

    return dp[len1][len2]
};