學(xué)習(xí)Levenshtein Distance算法
任意單個字符變動有3種情況昆婿，替換菲饼，增加和刪除：
1. 如果對應(yīng)的字符相同吵护，則從它的左，斜或者上方選取最小值达布，直接填寫
2. 如果對應(yīng)的字符不相同团甲，則從它的左，斜或者上方選取最小值黍聂，+1后填寫
括號內(nèi)部表示需要進行移動的步數(shù)
- 情況一：從ab到ac的變動
x位置 字符不相等(b!==c)躺苦，但是 i位置變動最小，所以從i位置的數(shù)值加1产还，斜線說明說替換
a b
a i(0) j(1)
c l(1) x
// x=1
- 情況二：從acd到ac的變動
x位置 字符不相等(b!==c)匹厘，但是 m位置變動最小，所以從m位置的數(shù)值加1脐区，橫向說明增加
a c d
a i(0) j(1) k(2)
c l(1) m(0) x
// x=1
- 情況三：從ab到abc的變動
x位置 字符不相等(b!==c)愈诚，但是 l位置變動最小，所以從l位置的數(shù)值加1，豎向說明減少
a b
a i(0) j(1)
b k(1) l(0)
c m(2) x
// x=1
每一次的判斷所確定的最小變動數(shù)炕柔，又是下一次判斷變動的基礎(chǔ)
function minED(a,b){
// 先創(chuàng)建a和b的二維數(shù)組（橫豎都額外多一行酌泰，作為第一個字符比較的基礎(chǔ)）
let arr=Array(b.length+1).fill(null);
for(let i=0;i<arr.length;i++){
arr[i]=Array(a.length+1).fill(null);
if(i===0){
for(let j=0;j<arr[0].length;j++){arr[0][j]=j;}
}
arr[i][0]=i;
}
// 對每一個字符進行比較，利用上一次比較的基礎(chǔ)
for(let i=1;i<arr.length;i++){
for(let j=1;j<arr[i].length;j++){
let count=0;
if(b[i-1]!==a[j-1]){
count++;
}
arr[i][j]=Math.min(arr[i-1][j-1],arr[i-1][j],arr[i][j-1])+count;
}
}
return arr[b.length][a.length]
}
let a='abcd',b="adbc"
minED(a,b)
let a='abcd',b="adbc"
minED(a,b)
// 輸出數(shù)據(jù)：
[ [ 0, 1, 2, 3, 4 ],
[ 1, 0, 1, 2, 3 ],
[ 2, 1, 1, 2, 2 ],
[ 3, 2, 1, 2, 3 ],
[ 4, 3, 2, 1, 2 ] ]
因此從'abcd'變動到'adbc'匕累，最小移動步數(shù)是2
