資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究JavaScript 中的 Levenshtein 距離
Levenshtein 距離
Levenshtein 距離是一個字串度量，用於測量兩個序列之間的差異。它是將一個單詞更改為另一個單詞所需的最小單字元編輯次數。
例如 -
假設我們有這兩個字串 -
const str1 = 'hitting'; const str2 = 'kitten';
這兩個字串之間的 Levenshtein 距離是 3，因為我們需要進行這三個編輯 -
kitten → hitten（用 "h" 替換 "k"）
hitten → hittin（用 "i" 替換 "e"）
hittin → hitting（在末尾插入 "g"）
我們需要編寫一個 JavaScript 函式，該函式輸入兩個字串並計算它們之間的 Levenshtein 距離。
示例
以下為程式碼 -
const str1 = 'hitting';
const str2 = 'kitten';
const levenshteinDistance = (str1 = '', str2 = '') => {
const track = Array(str2.length + 1).fill(null).map(() =>
Array(str1.length + 1).fill(null));
for (let i = 0; i <= str1.length; i += 1) {
track[0][i] = i;
}
for (let j = 0; j <= str2.length; j += 1) {
track[j][0] = j;
}
for (let j = 1; j <= str2.length; j += 1) {
for (let i = 1; i <= str1.length; i += 1) {
const indicator = str1[i - 1] === str2[j - 1] ? 0 : 1;
track[j][i] = Math.min(
track[j][i - 1] + 1, // deletion
track[j - 1][i] + 1, // insertion
track[j - 1][i - 1] + indicator, // substitution
);
}
}
return track[str2.length][str1.length];
};
console.log(levenshteinDistance(str1, str2));輸出
以下是在控制檯上的輸出 -
3
更新於： 2020 年 12 月 11 日
8K+ 瀏覽量
廣告