题解 | #编辑距离(一)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str1 string字符串
 * @param str2 string字符串
 * @return int整型
 */
function editDistance(str1, str2) {
    // write code here
    return resolve3(str1, str2);
}

/**
 * 暴力解法
 */

function resolve(str1, str2) {
    const n1 = str1.length,
        n2 = str2.length;

    // 定义 dp[i][j] 返回 s1[0, ..., i] 和 s2[0, ... j] 的最小编辑距离
    const helper = (i, j) => {
        // i、j 是 索引，当一个字符走完，删除另外一个字符 索引 + 1 的字符
        if (i === -1) return j + 1;
        if (j === -1) return i + 1;

        if (str1[i] === str2[j]) {
            return helper(i - 1, j - 1); // 啥都不做
        } else {
            // 穷举 插入、删除、修改三种操作，然后选一个最小操作数
            return Math.min(
                // s1 插入，s2 的指针往前走一步，操作数加1
                helper(i, j - 1) + 1, // 插入
                // s1 删除， s1 的指针往前走一步，操作数加1
                helper(i - 1, j) + 1, // 删除
                // 替换，两个指针都往前走一步，操作数加1
                helper(i - 1, j - 1) + 1 // 替换
            );
        }
    };

    return helper(n1 - 1, n2 - 1);
}

/**
 * 备忘录优化
 */

function resolve2(str1, str2) {
    const n1 = str1.length,
        n2 = str2.length;

    // 这里填充为最大值
    const memory = Array(n1)
        .fill()
        .map(() => Array(n2).fill(Infinity));

    // 定义 dp[i][j] 返回 s1[0, ..., i] 和 s2[0, ... j] 的最小编辑距离
    const helper = (i, j, memory) => {
        // i、j 是 索引，当一个字符走完，删除另外一个字符 索引 + 1 的字符
        if (i === -1) return j + 1;
        if (j === -1) return i + 1;

        if (memory[i][j] !== Infinity) {
            return memory[i][j];
        }

        if (str1[i] === str2[j]) {
            memory[i][j] = helper(i - 1, j - 1, memory); // 啥都不做
        } else {
            // 穷举 插入、删除、修改三种操作，然后选一个最小操作数
            memory[i][j] = Math.min(
                // s1 插入，s2 的指针往前走一步，操作数加1
                helper(i, j - 1, memory) + 1, // 插入
                // s1 删除， s1 的指针往前走一步，操作数加1
                helper(i - 1, j, memory) + 1, // 删除
                // 替换，两个指针都往前走一步，操作数加1
                helper(i - 1, j - 1, memory) + 1 // 替换
            );
        }

        return memory[i][j];
    };

    return helper(n1 - 1, n2 - 1, memory);
}

/**
 * 迭代优化
 */

function resolve3(str1, str2) {
    const n1 = str1.length,
        n2 = str2.length;
    // dp[i][j] 存储 s1[0, ...i-1] 变成 s2[0, ...., j-1]的最小编辑距离
    // 这里表格的初始值填充为0
    const dp = Array(n1 + 1)
        .fill()
        .map(() => Array(n2 + 1).fill(0));

    // base case 初始化
    for (let i = 1; i <= n1; i++) dp[i][0] = i;

    for (let j = 1; j <= n2; j++) dp[0][j] = j;

    // 自底向上
    for (let i = 1; i <= n1; i++) {
        for (let j = 1; j <= n2; j++) {
            if (str1[i - 1] === str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    dp[i][j - 1] + 1,
                    dp[i - 1][j] + 1,
                    dp[i - 1][j - 1] + 1
                );
            }
        }
    }

    return dp[n1][n2];
}

module.exports = {
    editDistance,
};

后续把图解过程补上。

具有重叠子问题的题是如何从暴力递归一步一步优化到动态规划