题解 | #最小编辑代价#

/**
 * min edit cost
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @param ic int整型 insert cost
 * @param dc int整型 delete cost
 * @param rc int整型 replace cost
 * @return int整型
 */
function minEditCost( str1 ,  str2 ,  ic ,  dc ,  rc ) {
    // write code here
    /** 动态规划 */
    // 状态： dp[i][j]
    // 状态转移：当str1[i] !== str2[j] dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
    //         当str1[i] === str2[j] dp[i][j] = dp[i-1][j-1]

    const l1 = str1.length+1;
    const l2 = str2.length+1;

    const dp = new Array(l1).fill(0).map(() => new Array(l2).fill(0));

    for (let i=0; i<l2; i++) {
        dp[0][i] = i*ic;
    }

    for (let i=0; i<l1; i++) {
        dp[i][0] = i*dc;
    }

    for (let i=1; i<l1; i++) {
        for (let j=1; j<l2; j++) {
            if (str1[i-1] === str2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                const del= dp[i-1][j] + dc
                const insert = dp[i][j-1] + ic
                const replace = dp[i-1][j-1] + rc
                dp[i][j] = Math.min(del, insert, replace)
            } 
        }
    }
   return dp[l1-1][l2-1]

}
module.exports = {
    minEditCost : minEditCost
};