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

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

// 方法一：暴力递归+哈希表存储= 记忆化搜索
void async function () {
    const word1 = await readline();
    const word2 = await readline();
    const map = new Map();
    const dfs = (i,j) => {
        if(i < 0 || j < 0) return i < 0?j+1:i+1;//一个字符串已经匹配完了
        if(map.has(i+"#"+j)) return map.get(i+"#"+j);
        if(word1.charAt(i) === word2.charAt(j)) return dfs(i-1,j-1);
        map.set(i+"#"+j,Math.min(dfs(i-1,j),dfs(i,j-1),dfs(i-1,j-1)) +1);
        return map.get(i+"#"+j);
    }
    console.log(dfs(word1.length-1,word2.length-1));
}()
// 方法二：动态规划
void async function () {
    const word1 = await readline();
    const word2 = await readline();
    const dp = Array.from(Array(word1.length+1),()=>Array(word2.length+1).fill(0));
    for(let i = 0; i <= word1.length; i++ ){
        for(let j = 0; j <= word2.length; j++ ){
            if(i === 0){
                dp[i][j] = j;
            }else if(j === 0){
                dp[i][j] = i;
            }else{
                let cost = word1.charAt(i-1) === word2.charAt(j-1)?0:1;
                dp[i][j] = Math.min(dp[i-1][j-1]+cost,dp[i-1][j]+1,dp[i][j-1]+1);
            }
        }
    }
    console.log(dp[word1.length][word2.length]);
}()