72. 编辑距离

[Geekhyt]

原题链接

状态定义

定义 dp[i][j]：word1 的前 i 个字符和 word2 的前 j 个字符的编辑距离。

更通俗的说，就是 word1 的前 i 个字符，变成 word2 的前 j 个字符，最少需要多少步。

把大象放进冰箱需要几步？ ：）

举个例子：

word1 = "horse", word2 = "ros"

dp[4][3] = x 也就是 "hors" 和 “ros” 的编辑距离，即把 "hors" 变成 “ros” 最少需要 x 步。

状态转移方程

1. word[i] === word[j] 时，dp[i][j] = dp[i - 1][j - 1]

2. word[i] !== word[j] 时，dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1

理解

1. 当两个字符串的最后一个字符相等时，则此时它们的编辑距离便和它们去掉最后一个字符后的编辑距离相等。

dp[i][j] = dp[i - 1][j - 1]

2. 当两个字符串的最后一个字符不相等时，编辑距离按照题意我们需要取三种操作情况的最小值。

• 插入：dp[i][j] = dp[i][j - 1] + 1
• 删除：dp[i][j] = dp[i - 1][j] + 1
• 替换：dp[i][j] = dp[i - 1][j - 1] + 1

分别理解：

• word2 较长时，需要从 word1 插入，也就是相当于从 word2 删去一个字符，与 word1 后面加上的字符匹配(操作次数+1)： dp[i][j] = dp[i][j - 1] + 1

• word1 较长时，需要从 word1 删除(操作次数+1)： dp[i][j] = dp[i - 1][j] + 1

• 当两个字符串长度相同，但新增字符不同时，进行替换(操作次数+1)： dp[i][j] = dp[i - 1][j - 1] + 1

初始化

考虑边界，当一个字符串与空字符串进行比较时，非空字符串的长度就是编辑距离。

const minDistance = function(word1, word2) {
    let n1 = word1.length
    let n2 = word2.length
    const dp = Array.from(Array(n1 + 1), () => Array(n2 + 1).fill(0))
    for (let i = 0; i <= n1; i++) {
        dp[i][0] = i
    }
    for (let j = 0; j <= n2; j++) {
        dp[0][j] = j
    }
    for (let i = 1; i <= n1; i++) {
        for (let j = 1; j <= n2; 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[n1][n2]
}

• 时间复杂度: O(m * n)
• 空间复杂度: O(m * n)