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

计算字符串的编辑距离

https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314

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

void (async function () {
    // Write your code here
    // while(line = await readline()){
    //     let tokens = line.split(' ');
    //     let a = parseInt(tokens[0]);
    //     let b = parseInt(tokens[1]);
    //     console.log(a + b);
    // }
    let line1 = await readline();
    let line2 = await readline();
    // console.log(line1.length,line2.length)
    const dp = new Array(line1.length).fill(0).map(() => {
        return new Array(line2.length).fill(0);
    });
    function getValidVal(i,j){
        if(i==-1&&j==-1){
            return 0
        }else if(i==-1&&j!=-1){
            return j+1
        }else if(i!=-1&&j==-1){
            return i+1
        }else{
        // console.log(i,j,dp[i][j])
            return dp[i][j]
        }
    }
    for (let i = 0; i < line1.length; i++) {
        for (let j = 0; j < line2.length; j++) {
            if (line1[i] == line2[j]) {
                    dp[i][j] = 0 + getValidVal(i-1,j-1);
                
            } else {
                    dp[i][j] =
                        1 +
                        Math.min(getValidVal(i-1,j-1), getValidVal(i-1,j), getValidVal(i,j-1));
                // if(i==line1.length-1){
                //     console.log(i,j,dp[i][j],dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
                // }
            }
        }
    }
    // console.log(dp[line1.length-1]);
    console.log(dp[line1.length - 1][line2.length - 1]);
})();

全部评论

相关推荐

今天 17:07
沈阳大学 Java
点赞 评论 收藏
分享
04-13 18:10
门头沟学院 Java
想熬夜的小飞象在秋招:被腾讯挂了后爸妈以为我失联了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务