最短编辑距离
程序员文章站
2022-06-24 14:06:09
最短编辑距离 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'))