Levenshtein in JS: Opus 4.7 vs GPT-5.5 vs Gemini 3.5 Flash

function levenshtein(a, b) {
  if (typeof a !== 'string' || typeof b !== 'string') {
    throw new TypeError('Both arguments must be strings');
  }

  if (a === b) return 0;
  if (a.length === 0) return b.length;
  if (b.length === 0) return a.length;

  // Ensure a is the shorter string to minimize memory usage
  if (a.length > b.length) {
    [a, b] = [b, a];
  }

  let prev = new Array(a.length + 1);
  let curr = new Array(a.length + 1);

  for (let i = 0; i <= a.length; i++) {
    prev[i] = i;
  }

  for (let j = 1; j <= b.length; j++) {
    curr[0] = j;
    for (let i = 1; i <= a.length; i++) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1;
      curr[i] = Math.min(
        curr[i - 1] + 1,       // insertion
        prev[i] + 1,           // deletion
        prev[i - 1] + cost     // substitution
      );
    }
    [prev, curr] = [curr, prev];
  }

  return prev[a.length];
}

function runTests() {
  const tests = [
    // [a, b, expected, description]
    ['', '', 0, 'both empty strings'],
    ['', 'abc', 3, 'first empty, second non-empty'],
    ['abc', '', 3, 'first non-empty, second empty'],
    ['abc', 'abc', 0, 'identical strings'],
    ['a', 'b', 1, 'single substitution'],
    ['kitten', 'sitting', 3, 'classic kitten/sitting example'],
    ['flaw', 'lawn', 2, 'flaw/lawn'],
    ['gumbo', 'gambol', 2, 'gumbo/gambol'],
    ['book', 'back', 2, 'book/back'],
    ['abc', 'abcd', 1, 'single insertion at end'],
    ['abcd', 'abc', 1, 'single deletion at end'],
    ['abc', 'xabc', 1, 'single insertion at start'],
    ['intention', 'execution', 5, 'intention/execution'],
    ['sunday', 'saturday', 3, 'sunday/saturday'],
    ['café', 'cafe', 1, 'unicode substitution'],
    ['ABC', 'abc', 3, 'case sensitivity'],
  ];

  let passed = 0;
  let failed = 0;

  for (const [a, b, expected, desc] of tests) {
    const result = levenshtein(a, b);
    const ok = result === expected;
    if (ok) {
      passed++;
      console.log(`PASS: ${desc} -> levenshtein("${a}", "${b}") = ${result}`);
    } else {
      failed++;
      console.error(`FAIL: ${desc} -> levenshtein("${a}", "${b}") = ${result}, expected ${expected}`);
    }
  }

  // Verify symmetry on a few cases
  const symmetryPairs = [
    ['kitten', 'sitting'],
    ['abc', ''],
    ['intention', 'execution'],
  ];
  for (const [a, b] of symmetryPairs) {
    const d1 = levenshtein(a, b);
    const d2 = levenshtein(b, a);
    if (d1 === d2) {
      passed++;
      console.log(`PASS: symmetry levenshtein("${a}", "${b}") == levenshtein("${b}", "${a}") = ${d1}`);
    } else {
      failed++;
      console.error(`FAIL: symmetry levenshtein("${a}", "${b}")=${d1} != levenshtein("${b}", "${a}")=${d2}`);
    }
  }

  // Error handling test
  try {
    levenshtein(null, 'abc');
    failed++;
    console.error('FAIL: expected TypeError for non-string input');
  } catch (e) {
    if (e instanceof TypeError) {
      passed++;
      console.log('PASS: throws TypeError on non-string input');
    } else {
      failed++;
      console.error('FAIL: wrong error type for non-string input:', e);
    }
  }

  console.log(`\n${passed} passed, ${failed} failed`);
  return failed === 0;
}

runTests();

module.exports = { levenshtein, runTests };

function levenshteinDistance(a, b) { if (a === b) return 0; if (a.length === 0) return b.length; if (b.length === 0) return a.length;

const prev = Array.from({ length: b.length + 1 }, (_, i) => i); const curr = new Array(b.length + 1);

for (let i = 1; i <= a.length; i++) { curr[0] = i;

for (let j = 1; j <= b.length; j++) {
  const cost = a[i - 1] === b[j - 1] ? 0 : 1;

  curr[j] = Math.min(
    prev[j] + 1,      // deletion
    curr[j - 1] + 1,  // insertion
    prev[j - 1] + cost // substitution
  );
}

for (let j = 0; j <= b.length; j++) {
  prev[j] = curr[j];
}

}

return prev[b.length]; }

const assert = require("assert");

assert.strictEqual(levenshteinDistance("", ""), 0); assert.strictEqual(levenshteinDistance("", "abc"), 3); assert.strictEqual(levenshteinDistance("abc", ""), 3); assert.strictEqual(levenshteinDistance("abc", "abc"), 0); assert.strictEqual(levenshteinDistance("kitten", "sitting"), 3); assert.strictEqual(levenshteinDistance("flaw", "lawn"), 2); assert.strictEqual(levenshteinDistance("gumbo", "gambol"), 2); assert.strictEqual(levenshteinDistance("book", "back"), 2); assert.strictEqual(levenshteinDistance("a", "b"), 1); assert.strictEqual(levenshteinDistance("abc", "yabd"), 2);

console.log("All tests passed.");

/**
 * Computes the Levenshtein distance between two strings.
 * The Levenshtein distance is the minimum number of single-character edits
 * (insertions, deletions, or substitutions) required to change one string into another.
 * 
 * @param {string} str1 - The first string.
 * @param {string} str2 - The second string.
 * @returns {number} The Levenshtein distance between the two strings.
 */
function levenshteinDistance(str1, str2) {
    const len1 = str1.length;
    const len2 = str2.length;

    // Create a 2D array (matrix) of size (len1 + 1) x (len2 + 1)
    const matrix = Array.from({ length: len1 + 1 }, () => Array(len2 + 1).fill(0));

    // Initialize the first row and column
    for (let i = 0; i <= len1; i++) {
        matrix[i][0] = i;
    }
    for (let j = 0; j <= len2; j++) {
        matrix[0][j] = j;
    }

    // Fill the matrix
    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            const cost = str1[i - 1] === str2[j - 1] ? 0 : 1;
            matrix[i][j] = Math.min(
                matrix[i - 1][j] + 1,       // Deletion
                matrix[i][j - 1] + 1,       // Insertion
                matrix[i - 1][j - 1] + cost // Substitution
            );
        }
    }

    return matrix[len1][len2];
}

// ==========================================
// TEST SUITE
// ==========================================

function runTests() {
    const testCases = [
        { desc: "Empty strings", a: "", b: "", expected: 0 },
        { desc: "First string empty", a: "", b: "abc", expected: 3 },
        { desc: "Second string empty", a: "abc", b: "", expected: 3 },
        { desc: "Identical strings", a: "hello", b: "hello", expected: 0 },
        { desc: "Single character substitution", a: "a", b: "b", expected: 1 },
        { desc: "Single character insertion", a: "cat", b: "cats", expected: 1 },
        { desc: "Single character deletion", a: "cats", b: "cat", expected: 1 },
        { desc: "Case sensitivity validation", a: "Hello", b: "hello", expected: 1 },
        { desc: "Complex transition (kitten -> sitting)", a: "kitten", b: "sitting", expected: 3 },
        { desc: "Complex transition (intention -> execution)", a: "intention", b: "execution", expected: 5 },
        { desc: "Completely different strings of different lengths", a: "abcdef", b: "ghijk", expected: 6 }
    ];

    let passedAll = true;
    console.log("Running Levenshtein Distance Tests...\n");

    testCases.forEach(({ desc, a, b, expected }, index) => {
        const result = levenshteinDistance(a, b);
        if (result === expected) {
            console.log(`✓ Test ${index + 1} Passed: "${desc}"`);
            console.log(`  Inputs: "${a}" vs "${b}" | Result: ${result}\n`);
        } else {
            console.error(`✗ Test ${index + 1} Failed: "${desc}"`);
            console.error(`  Inputs: "${a}" vs "${b}"`);
            console.error(`  Expected: ${expected}, but Got: ${result}\n`);
            passedAll = false;
        }
    });

    if (passedAll) {
        console.log("All tests passed successfully!");
    } else {
        console.error("Some tests failed.");
    }
}

// Execute tests
runTests();