leetcode刷题 log day56（编辑距离总结篇～

• 583. 两个字符串的删除操作
  【思路】这道题只有删除操作，两个字符串相等时，步数不变，不相等时，只能做删除操作，删除有三种情况：删除 word1 或删除 word2 或者两个字符串都删除，取三种情况的最小值。

  var minDistance = function(word1, word2) {
    let dp = new Array(word1.length + 1).fill().map(() => 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] + 2);
      }
    }
    return dp[word1.length][word2.length];
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

• 72. 编辑距离
  【思路】只能说只要图画的够丑就不用加水印
  

  var minDistance = function(word1, word2) {
    let dp = new Array(word1.length + 1).fill().map(() => 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];
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16

编辑距离总结～

• 判断子序列：s 是否是 t 的子序列，dp[i][j] 两个字符串目前相等的个数：

  • 相等： dp[i][j] = dp[i - 1][j - 1] + 1；
  • 不相等：dp[i][j] = dp[i - 1][j]；

• 不同的子序列：计算 t 在 s 的子序列中出现的次数：

  • 相等：用 s[i - 1] 匹配 + 不用 s[i - 1] 匹配 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]；
  • 不相等：dp[i][j] = dp[i -1][j]；

• 两个字符串中的删除操作：

  • 相等：不做操作dp[i][j] = dp[i - 1][j - 1]；
  • 不相等：可以删除 word1 中的元素、删除 word2 中的元素或两个字符串都删除元素，三者取最小值 dp[i][j] = Math.min(dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1)；

• 编辑距离见上～

参考代码随想录：https://www.programmercarl.com/