字符串的编辑距离-动态规划
计算字符串的编辑距离
https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314?tpId=37&tqId=21275&rp=1&ru=/ta/huawei/&qru=/ta/huawei&difficulty=3&judgeStatus=&tags=/question-ranking
状态转移方程大家应该都知道
当word[i]==word[j]时,dp[i][j]=dp[i-1][j-1]
当word[i]!=word[j]时, dp[i][j]=1+Math.min(dp[i][j-1],dp[i-1][j-1],dp[i-1][j]);
其实我想请教一个问题,在js node中初始化二维数组以及赋值,有什么简便方法吗,我的方法好繁琐
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let data = [];
rl.on('line', function (line) {
data.push(line.split(''))
if(data.length==2){
let dp = new Array(data[0].length+1);
for(let i = 0; i < data[0].length+1; i++){//创建二维数组
dp[i]=new Array(data[1].length)
};
for(let j = 0; j < dp.length; j++){//初始化数组
if(j==0){
for(let k = 0; k < data[1].length+1 ; k++){
dp[j][k]=k
}
}
dp[j][0]=j
}
for(let row = 1;row < dp.length;row++){//根据状态转移方程实现动态规划
for(let column =1;column <data[1].length+1;column++){
if(data[0][row-1]==data[1][column-1]){
dp[row][column]=dp[row-1][column-1]
}
else{
dp[row][column]=Math.min(dp[row][column-1],dp[row-1][column],dp[row-1][column-1])+1
}
}
}
console.log(dp[data[0].length][data[1].length]);
data=[];
}
});