两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。

  • 输入: word1 = “sea”, word2 = “eat”

  • 输出: 2

  • 解释: 第一步将 “sea” 变为 “ea” ，第二步将 “eat “变为 “ea”

  • 输入：word1 = “leetcode”, word2 = “etco”

  • 输出：4

动态规划
dp[i][j] 表示 word1 的前 i 个和 word2 的前 j 个变的相同的最小步数。
当 word1[i - 1] == word2[j - 1] 时，无需改变最后一个，所以 dp[i][j] = dp[i - 1][j - 1]。
当 word1[i - 1] != word2[j - 1] 时，要么删除 word1[i - 1]，要么删除 word2[j - 1]，所以 dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var minDistance = function(word1, word2) {
    const m = word1.length, n = word2.length;
    const dp = new Array(m + 1).fill(0).map(_ => new Array(n + 1).fill(0));
    for (let j = 1; j <= n; j++) dp[0][j] = j;
    for (let i = 1; i <= m; i++) {
        dp[i][0] = i;
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
};