题解 | #计算字符串的编辑距离#

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 保存第一个字符串数组
const arr1 = []
// 保存第二个字符串数组
const arr2 = []
let row = 0 


rl.on('line', function (line) {
    row++
    if(row === 1){
        arr1.push(...line.split(''))
    }else {
        arr2.push(...line.split(''))
        // 保存画图二维数组，就是以两字符串为两边尽心画图
        const dp = new Array(arr1.length + 1).fill(0).map(()=>new Array(arr2.length+1).fill(0))
        // 给第一行赋值
        for(let i = 0; i < dp[0].length; i++){
            dp[0][i] = i
        }
        // 给第一列赋值
        for(let j = 0; j < dp.length; j++){
            dp[j][0] = j
        }

        // 这里就是填充二维数组了
        for(let i = 1; i < dp.length; i++){
            for(let j = 1; j < dp[0].length; j++){
                // 如果两个字符串相下标处的字符一样，因为i、j是从1开始的，但是我们两个字符串是从0开始的，所以
                // 这里是 i - 1 == j-1
                if(arr1[i-1] === arr2[j-1]){
                    // 这里因为第一行与第一列在上面已经赋值，所以，从i、j  为1开始
                    dp[i][j] = dp[i-1][j-1]
                }else {
                    // 取斜上方、上方、左边三值的最小值、然后加1
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1
                }
            }
        }
        
        console.log(dp[arr1.length][arr2.length])

    }
});