题解 | BM75 编辑距离(一)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str1 string字符串
 * @param str2 string字符串
 * @return int整型
 */
function editDistance(str1, str2) {
    // write code here
    let len1 = str1.length;
    let len2 = str2.length;
    let dp = Array.from(Array(len1 + 1), () => new Array(len2 + 1).fill(1005));
    dp[0][0] = 0;
    // console.log(dp);
    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 {
                // 若当前两个字符不同，则需要找出两个字符上一位，str1前一位str2当前位，
                // str1当前位str2前一位中变化最小的情况进行更新，并加上当前需要变化的1
                dp[i][j] =
                    Math.min(
                        dp[i - 1][j - 1],
                        Math.min(dp[i - 1][j], dp[i][j - 1])
                    ) + 1;
            }
        }
    }
    // console.log(dp);
    return dp[len1][len2];
}
module.exports = {
    editDistance: editDistance,
};