583. Delete Operation for Two Strings

source: https://leetcode.com/problems/delete-operation-for-two-strings/

Question

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

从最长公共子序列CLS求出

这题其实是1143题的姐妹题，本质上是相同问题。

最后他们要删除的那个部分，其实就是CLS。

/**
 * from cls
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    // 1143
    var longestCommonSubsequence = function (text1, text2) {
        const dp = new Array(text1.length + 1).fill().map(() => new Array(text2.length + 1).fill(0));
        for (let i = text1.length - 1; i >= 0; i--) {
            for (let j = text2.length - 1; j >= 0; j--) {
                if (text1[i] === text2[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
                else dp[i][j] = Math.max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
        return dp[0][0];
    };
    const cls = longestCommonSubsequence(word1, word2);
    return word1.length + word2.length - cls * 2;
};

递归法

这里的find(i, j)，代表text1[i..]和text[j..]之间要删除的最小步数。

/**
 * 递归+备忘录
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    const cache = {};
    const getCacheData = (i, j) => {
        const key = `${[i, j]}`;
        if (cache[key] === undefined) cache[key] = find(i, j);
        return cache[key];
    };
    const find = (i, j) => {
        if (i === word1.length) return word2.length - j;
        if (j === word2.length) return word1.length - i;
        if (word1[i] === word2[j]) return getCacheData(i + 1, j + 1);
        else return Math.min(getCacheData(i + 1, j + 1) + 2, getCacheData(i + 1, j) + 1, getCacheData(i, j + 1) + 1);
    };
    return find(0, 0);
};

动态规划

dp类似：

/**
 * dp
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    const dp = new Array(word1.length + 1).fill().map(() => new Array(word2.length + 1).fill(0));
    for (let i = 0; i < word1.length; i++) dp[i][word2.length] = word1.length - i;
    for (let j = 0; j < word2.length; j++) dp[word1.length][j] = word2.length - j;
    for (let i = word1.length - 1; i >= 0; i--) {
        for (let j = word2.length - 1; j >= 0; j--) {
            if (word1[i] === word2[j]) dp[i][j] = dp[i + 1][j + 1];
            else dp[i][j] = Math.min(dp[i + 1][j + 1] + 2, dp[i + 1][j] + 1, dp[i][j + 1] + 1);
        }
    }
    return dp[0][0];
};

End

问题之间有相似之处，学会问题的转换，举一反三。