题解 | #计算字符串的编辑距离#
计算字符串的编辑距离
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]); })();