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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str1 string字符串 
 * @param str2 string字符串 
 * @return int整型
 */
function editDistance( str1 ,  str2 ) {
    // write code here
    const len1 = str1.length;
    const len2 = str2.length;
    //定义dp[i][j]为，一个字符串前i个子字符，变成第二个字符串前j个子字符的最小操作数
    const dp = Array.from({length:len1+1},()=>Array.from({length:len2+1},()=>0));
    //状态方程初始化
    for(let i = 0; i <= len1; i++) {
        dp[i][0]=i;
    }
    for(let i = 0;i <= len2; i++) {
        dp[0][i] = i;
    }
    for(let i = 1; i <= len1; i++) {
        for(let j =1; j <= len2; j++) {
            if(str1[i-1] === str2[j-1]){
                dp[i][j] = dp[i-1][j-1];
            }else{
                dp[i][j] = Math.min(
                    dp[i-1][j],//删除str1[i]
                    dp[i-1][j-1],//str1[i]替换成str2[j]
                    dp[i][j-1]//str1[i]后添加str2[j]
                )+1;
            }
        }
    }
    return dp[len1][len2];
}
module.exports = {
    editDistance : editDistance
};