暑期算法 第九题

题目

给你两个单词 word1word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

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

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

来源:LeetCode-72

题解

const minDistance = (word1, word2) => {
    let dp = Array.from(Array(word1.length + 1), () => Array(word2.length+1).fill(0));

    for(let i = 1; i <= word1.length; i++) {
        dp[i][0] = i; 
    }

    for(let j = 1; j <= word2.length; j++) {
        dp[0][j] = j;
    }

    for(let i = 1; i <= word1.length; i++) {
        for(let j = 1; j <= word2.length; 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][j-1] + 1, dp[i-1][j-1] + 1);
            }
        }
    }
    
    return dp[word1.length][word2.length];
};

题析

这又又又是一道动态规划题,但比较难,仍是抓住三个要点:

定义数组元素的含义

dp[i][j] 表示以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2,最近编辑距离为dp[i][j]

有点难想象到,但逻辑是寻的通的。

找出数组元素间的关系式

if (word1[i - 1] == word2[j - 1])
    不操作
if (word1[i - 1] != word2[j - 1])
    增
    删
    换

word1[i - 1] == word2[j - 1]时,即当前字符是对应相同的,所以不需要变动,dp[i][j] = dp[i - 1][j - 1],当前格子的dp等于左上角的dp,这里需要回到dp的定义,会有点难理解。可以这样看,当前字符对比相同时,需要跳过当前而对比下一个字符,word1和word2对比下一个字符就相当于dp[i + 1][j + 1],因为上一个字符相同,所以不需要操作,所以编辑距离就等于dp[i][j],由于我们需要的是下一个字符的推导式,所以可以等价于dp[i][j] = dp[i - 1][j - 1](全部变量自减1)。

word1[i - 1] != word2[j - 1]时,即当前字符是对应不同的,所以需要变动,可能是增删换其中一个。增相当于word1++,可以在矩阵中看做往下一格。增相当于word2++,可以在矩阵中看做往右一格。换相当于word1++与word2++,可以在矩阵中看做往右下一格。无论怎么操作,编辑距离都要加1。对于如何操作,自然选择最小的编辑距离。所以有dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1

找出初始条件

dp[i][0] = idp[0][j] = j

题外

dp的定义非常重要,如何定义dp仍需不断的练习。此题动态规划非常巧妙,可以多看几遍。