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

DP数组应该保存什么？

两个字符串的问题可以考虑用二维DP数组，由于题目要求str1转换为str2所需要的最小操作数，因此dp[i][j]应该设置为str1中从开头到第i个字符的子串转换为str2中从开头到第j个字符的子串所需要的最小操作数。

最小子问题

• 当str1为空串时，即i等于0时，str2每增加一个字符，str1转换为str2都要插入一个字符，即操作数+1。
• 当str2为空串时，即j等于0时，str1每增加一个字符，str1转换为str2都要删除一个字符，即操作数+1。
• 通过以上两种最小子问题情况可以初始化二维DP数组的边界。

如何思考状态转移方程？

• 对于str1的i位置和str2的j位置，如果这两个位置的字符相同，当前位置不需要操作，此时dp[i][j] = dp[i-1][j-1]。
• 如果这两个位置的字符不相同，则当前位置必然要进行一次操作，当前位置操作数必然增加1，但要判断当前位置哪种操作代价最小。当前位置一共有三种操作情况，分别为修改，插入，删除。当需要str1修改当前字符跟str2相同时，当前操作数为dp[i][j] = dp[i-1][j-1]+1;当需要str1删除字符使其跟str2相同时，dp[i][j] = dp[i-1][j]+1;当需要str1添加字符使其跟str2相同时，dp[i][j] = dp[i][j-1]+1。取以上三种情况的最小值为当前位置的操作数即可。

参考

https://blog.nowcoder.net/n/918b332881e043898fa2b77d973ec375?f=comment

https://blog.nowcoder.net/n/d61f470c6de34a85870e47e5e4f336e4?f=comment

/*
 * @Author: LibraStalker **********
 * @Date: 2023-04-12 09:38:17
 * @FilePath: BM75-编辑距离(一).js
 * @Description: 
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str1 string字符串 
 * @param str2 string字符串 
 * @return int整型
 */
function editDistance( str1 ,  str2 ) {
    // write code here
    const dp = Array.from(new Array(str1.length+1), () => new Array(str2.length+1).fill(0));

    // 初始状态
    for (let i = 1; i <= str1.length; ++i) {
        dp[i][0] = dp[i-1][0]+1;  // 当str2为空字符串时，str1每增加一个字符，str1都相当于要进行一次删除操作才能转换为str2
    }
    for (let j = 1; j <= str2.length; ++j) {
        dp[0][j] = dp[0][j-1]+1;  // 当str1为空字符串时，str2每增加一个字符，str1都相当于要进行一次插入操作才能转换为str2
    }

    for (let i = 1; i <= str1.length; ++i) {
        for (let j = 1; j <= str2.length; ++j) {
            // 对于str1的i位置和str2的j位置，如果这两个位置的字符相同，则不需要操作，如果不同则必然进行一次操作，然后判断是修改，删除，插入哪种代价较低，再此基础上增加一次操作
            dp[i][j] = str1[i-1] === str2[j-1] ? dp[i-1][j-1] : Math.min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])+1;  // dp[i][j-1]表示进行插入操作，dp[i-1][j]表示进行删除操作
        }
    }

    return dp[str1.length][str2.length];
}

module.exports = {
    editDistance : editDistance
};