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

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
let lines = []
void async function () {
    // Write your code here
    while(line = await readline()){
        lines.push(line)
        if(lines.length===2){
            getMin(lines)
        }
    }
}()

function getMin(lines){
    let one = lines[0].split('')
    let two  = lines[1].split('')
    let dp = new Array(one.length).fill(0)
    dp = dp.map(()=>{return new Array(two.length).fill(0)})
    dp[-1]=dp[0].map((item,index)=>{return index+1})
    dp.forEach((item,index)=>{
        dp[index][-1]=index+1
    })
    dp[-1][-1]=0
    // console.log(dp[0][-1],dp[-1][0],dp[-1][-1])
    for(let i = 0;i<one.length;i++){
        for(let j = 0;j<two.length;j++){
            if(one[i]===two[j]){
                dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j]+1,dp[i][j-1]+1)
            }else{
                dp[i][j]=Math.min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1)           }
        }
    }
    console.log(dp[one.length-1][two.length-1])
}