Cocolib

Appearance

On this page

两个字符串的删除操作 ​

TIP

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

思路 ​

  • 这题本质上还是求最长公共子序列
js
var minDistance = function(word1, word2) {
    let dp = Array(word1.length +1).fill().map(() => Array(word2.length + 1).fill(0))
    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] + 1
            }else{
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
            }
        }
    }
    let res = word1.length - dp[word1.length][word2.length]
    res += word2.length - dp[word1.length][word2.length]
    return res
};