最短編輯距離 js function levenshteinDistance(a,b){ //生成表 const distanceMatix = Array(a.length + 1).fill(null).map(() = Array(b.length + 1).fill(null)) //第一行 ...
最短編輯距離
1.第一行表示從ME到空字元所要刪除的字元的所以情況
2.第一列表示從空字元到MY所需要插入字元的所有情況
3.斜箭頭表示相同字元不需要替換,不相同字元所有替換次數的所有情況function levenshteinDistance(a,b){
//生成表
const distanceMatix = Array(a.length + 1).fill(null).map(() => Array(b.length + 1).fill(null))
//第一行的修改次數
for(let i =0; i <= a.length; i++){
distanceMatix[i][0] = i;
}
//第一列的修改次數
for(let j = 0; j <= b.length; j++){
distanceMatix[0][j] = j;
}
for(let i = 1; i <= a.length; i++){
for(let j = 1; j <= b.length; j++){
let indicator = a[i - 1] === b[j - 1] ? 0 : 1
distanceMatix[i][j] = Math.min(
distanceMatix[i][j-1] + 1, //刪除操作的總修改次數
distanceMatix[i-1][j] + 1,//插入修改的總修改次數
distanceMatix[i - 1][j - 1] + indicator //不一樣就替換的次數
)
}
}
//
return distanceMatix[a.length][b.length]
}
console.log(levenshteinDistance('my name is a','y me s b'))
