最端编辑距离算法

参考资料：经典动态规划问题：最短编辑距离算法的原理及实现 (opens new window)

给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数，你总共三种操作方法：插入一个字符、删除一个字符、替换一个字符

考察点：Levenshtein Distance 算法，react中使用场景，多应用于模糊匹配

const str1 = 'study'
const str2 = 'stduy1'

/*
     0 s t u d y
   0 0 1 2 3 4 5
   s 1
   t 2
   u
   d
   y
*/
//暴力解法： 空间复杂度o(n^2), 时间复杂度o(n^2)
function levenshtein1(str1, str2) {
    let len1 = str1.length
    let len2 = str2.length
    let ary = Array.from(new Array(len2 + 1), () => new Array(len1 + 1))
    //let ary = []
    for (let i = 0; i <= len1; i++) {
        //ary[i] = []
        for (let j = 0; j <= len2; j++) {
            if (i == 0) {
                ary[i][j] = j
            } else if (j == 0) {
                ary[i][j] = i
            } else {
                ary[i][j] = Math.min(
                    ary[i - 1][j] + 1, 
                    ary[i][j - 1] + 1, 
                    str1[i] === str2[j] ? ary[i - 1][j - 1] : ary[i - 1][j - 1] + 1)
            }
        }
    }
    return ary[len1][len2]
}

//滚动数组：空间复杂度o(n*2), 时间复杂度o(n^2)
function levenshtein2(str1, str2) {
    let len1 = str1.length
    let len2 = str2.length
    let ary = new Array(len1 + 1)
    for(let i=0; i<=len1; i++){
        ary[i] = i
    }
    let aryT = [].concat(ary)
    for(let j=1; j<=len2; j++){
        ary[0] = j;
        for (let i=1; i<=len1; i++){
            ary[i] = Math.min(
                ary[i-1] + 1,
                aryT[i] + 1,
                str1[i] === str2[j] ? aryT[i-1] : aryT[i-1] + 1
            )
        }
        aryT = [].concat(ary)
    }
    return ary[len1]
}

console.log(levenshtein1(str1, str2))
console.log(levenshtein2(str1, str2))