levenshtein
unknown
javascript
a month ago
1.2 kB
5
Indexable
Never
function levenshteinDistance(s1, s2) { const len1 = s1.length; const len2 = s2.length; // Create a 2D array to store the distances const dp = Array.from({ length: len1 + 1 }, () => Array(len2 + 1).fill(0)); // Initialize the first row and column for (let i = 0; i <= len1; i++) { dp[i][0] = i; } for (let j = 0; j <= len2; j++) { dp[0][j] = j; } // Compute the distances for (let i = 1; i <= len1; i++) { for (let j = 1; j <= len2; j++) { const cost = s1[i - 1] === s2[j - 1] ? 0 : 1; dp[i][j] = Math.min( dp[i - 1][j] + 1, // Deletion dp[i][j - 1] + 1, // Insertion dp[i - 1][j - 1] + cost // Substitution ); } } // The distance is the value in the bottom-right corner of the matrix return dp[len1][len2]; } // Example usage const str1 = "You are my favorite person"; const str2 = "Thou art mine most favored person"; const distance = levenshteinDistance(str1, str2) const similarity = 1 - distance / Math.max(str1.length, str2.length); const similarityPercent = similarity.toFixed(4) * 100
Leave a Comment