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

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

function fn(str1, str2) {
    // dp[i][j]表示str1[0:i] 到 str2[0:j]的编辑距离
    let dp = new Array(str1.length  + 1).fill(-1).map(()=>new Array(str2.length + 1).fill(-1))
    // i=0时，空字符串到str2[0:j]的距离为添加j个字符，即j
    for(let j = 0; j <= str2.length; j++) {
        dp[0][j] = j
    }
    // j= 0时，str1[0:i]到空字符串的距离为删除i个字符，即i
    for(let i = 0; i <= str1.length; i++) {
        dp[i][0] = i
    }
    for(let i = 1; i <= str1.length; i++) {
        for(let j = 1; j <= str2.length; j++) {
            // 求替换，插入，删除三种操作最小的值
           // 替换 ：str1[i]===str2[j]时，dp[i][j] = dp[i-1][j-1](无需操作)。 str1[i]!==str2[j]时，dp[i][j] = dp[i - 1][j - 1] + 1（进行一次替换）
           // 插入：dp[i][j] = dp[i][j - 1] + 1
           // 删除 dp[i][j] = dp[i - 1][j] + 1
           // 再求最小值
           if(str1[i - 1] === str2[j - 1]) {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1])
           } else {
                
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) +  1
           }   
        }
    }
    return dp[str1.length][str2.length]
}



void async function () {
    // Write your code here
    while(line = await readline()){
        let str2 = await readline()
        console.log(fn(line, str2))
    }
}()