编辑距离（一）

代码

/**
 * @param str1 string字符串
 * @param str2 string字符串
 * @return int整型
 */
function editDistance(str1, str2) {
    // write code here
    const m = str1.length,
        n = str2.length;
    // dp[i][j] 表示，str2 的首字母到 i ，str1 的首字母到 j 的编辑距离
    const dp = new Array(n + 1).fill(1).map(() => new Array(m + 1).fill(0));
    // 行初始化，str1 首字母为空字符串时，编辑距离为上一次的编辑距离 + 1
    // 也就是上一个 str2 字符所在下标 i - 1 的编辑距离 + 1
    for (let i = 1; i <= n; i++) {
        dp[i][0] = dp[i - 1][0]; // 也可以直接写 i，为了理解清 dp[i][j] 的含义这里采用 dp[i - 1][0]
    }
    // 列的初始化类似行初始化，str2 的首字母为空字符串时，相对于 str1 当前位置 j 的编辑距离
    for (let j = 1; j <= m; j++) {
        dp[0][j] = dp[0][j - 1]; // j
    }
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (str2[i - 1] === str1[j - 1])
                // 不需要编辑，直接选取回退当前两个字符的情况
                // 两个字符相同，这多出来的字符就不用操作，操作次数与两个子串的前一个相同
                // 因此有dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i - 1][j - 1]dp[i][j]=dp[i−1][j−1]
                dp[i][j] = dp[i - 1][j - 1];
            else {
                // 需要编辑，从前面中选取最小的加以编辑
                // 递推公式应该由状态转移到的情况得出：
                // 两个字符不相同，那么这两个字符需要编辑
                // 但是此时的最短的距离不一定是由修改子串得出，也有可能是删除某个字符或者增加某个字符
                // 因此我们选取这三种情况的最小值增加一个编辑距离
                // 即，dp[i][j]=min(dp[i−1][j−1],min(dp[i−1][j],dp[i][j−1]))+1
                dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        }
    }
    // 拿到下标为 m ， n 的编辑距离，总的编辑距离有前面各个子编辑距离得出
    return dp[n][m];
}