72. Edit Distance

source: https://leetcode.com/problems/edit-distance/

Question

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

递归法

这里的i和j对应两个词的数组下标。

dp(i, j)这个函数代表的意义就是，从word1[i]开始的词，转换为word2[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] = dp(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, j + 1) + 1, getCacheData(i + 1, j) + 1, getCacheData(i + 1, j + 1) + 1);
    };
    return find(0, 0);
};

动态规划

这里的二维数组dp table，其实就是递归法里的dp(i, j), 计算的顺序也是相同的。只不过递归法是自上而下，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 = 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][j - 1] + 1,
                dp[i - 1][j] + 1,
                dp[i - 1][j - 1] + 1
            );
        }
    }
    return dp[word1.length][word2.length];
};

End

对于两个字符串的问题，可以考虑用dp table的方式去解，即分别为i,j指向两个字符串的某个字符，然后寻找状态转移的方式。