兩個字符串的刪除操作

力扣題目鏈接
法一

1. dp數(shù)組含義：
   dp[i][j]:以i-1,j-1結尾的最少刪除個數(shù)
2. 遞推公式：
   dp[i]==dp[j-1],dp[i][j]=dp[i-1][j-1]
   dp[i]!=dp[j-1],dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2) 其中，,dp[i][j-1]+1包含了dp[i-1][j-1]+2，故可簡化為min(dp[i-1][j]+1,dp[i][j-1]+1)
3. 初始化：
   dp[i][0]=i,dp[0][j]=j, 相當于其中一個為空串，則操作次數(shù)為i/j
4. 遍歷順序
   順序

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

法二
利用最長公共子序列，
最后求得的結果=word1.length+word2.length-最長公共子序列*2

編輯距離

力扣題目鏈接

1. dp數(shù)組含義：
   dp[i][j]:以i-1,j-1結尾的最少刪除個數(shù)
2. 遞推公式：
   dp[i]==dp[j-1],dp[i][j]=dp[i-1][j-1]
   dp[i]!=dp[j-1],dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+1)
3. 初始化：
   dp[i][0]=i,dp[0][j]=j，相當于其中一個為空串，則操作次數(shù)為i/j
4. 遍歷順序
   順序

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