7. 两个字符串的最短路径

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

const lines = [];
rl.on('line', (line) => {
    let [A, B] = line.split(' ');
    let m = B.length;
    let n = A.length;
    let dp = new Array(1+n).fill(0).map((_,i)=>i);
    for(let i=1; i<=m; i++) {
        let prev = dp[0];
        dp[0] = i;
        for(let j=1; j<=n; j++) {
            const temp = dp[j];
            if (A[j-1] === B[i-1]) {
                dp[j] = prev + 1;
            } else {
                dp[j] = Math.min(dp[j], dp[j-1]) + 1;
            }
            prev = temp;
        }
    }
    console.log(dp[n]);
});