Khoảng cách Levenshtein
Khoảng cách Levenshtein là một thước đo chuỗi để đo sự khác biệt giữa hai chuỗi. Đây là số lượng chỉnh sửa ký tự đơn tối thiểu cần thiết để thay đổi một từ thành từ kia.
Ví dụ:
Xét hai chuỗi sau:
const str1 = 'hitting'; const str2 = 'kitten';
Khoảng cách Levenshtein giữa hai chuỗi này là 3 vì chúng ta cần thực hiện ba lần chỉnh sửa:
- kitten → hitten (thay thế "h" cho "k")
- hitten → hittin (thay thế "i" cho "e")
- hittin → hitting (chèn "g" ở cuối)
Chúng ta cần viết một hàm JavaScript nhận vào hai chuỗi và tính khoảng cách Levenshtein giữa chúng.
Ví dụ
Dưới đây là mã nguồn:
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, // xóa track[j - 1][i] + 1, // chèn track[j - 1][i - 1] + indicator, // thay thế ); } } return track[str2.length][str1.length]; }; console.log(levenshteinDistance(str1, str2));Kết quả
Đầu ra trên console:
3