levenshtein

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