This code calculates the Levenshtein distance between two strings, which represents the minimum number of edits (insertions, deletions, or substitutions) needed to transform one string into the other. It uses a dynamic programming approach to efficiently compute this distance.

Run example

npm run import -- "Find the levenshtein distance"

Find the levenshtein distance

function levDist(s, t) {
    var d = []; //2d matrix

    // Step 1
    var n = s.length;
    var m = t.length;

    if (n == 0) return m;
    if (m == 0) return n;

    //Create an array of arrays in javascript (a descending loop is quicker)
    for (var i = n; i >= 0; i--) d[i] = [];

    // Step 2
    for (var i = n; i >= 0; i--) d[i][0] = i;
    for (var j = m; j >= 0; j--) d[0][j] = j;

    // Step 3
    for (var i = 1; i <= n; i++) {
        var s_i = s.charAt(i - 1);

        // Step 4
        for (var j = 1; j <= m; j++) {

            //Check the jagged ld total so far
            if (i == j && d[i][j] > 4) return n;

            var t_j = t.charAt(j - 1);
            var cost = (s_i == t_j) ? 0 : 1; // Step 5

            //Calculate the minimum
            var mi = d[i - 1][j] + 1;
            var b = d[i][j - 1] + 1;
            var c = d[i - 1][j - 1] + cost;

            if (b < mi) mi = b;
            if (c < mi) mi = c;

            d[i][j] = mi; // Step 6

            //Damerau transposition
            if (i > 1 && j > 1 && s_i == t.charAt(j - 2) && s.charAt(i - 2) == t_j) {
                d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
            }
        }
    }

    // Step 7
    return d[n][m];
}
module.exports = levDist;

/**
 * Calculates the Levenshtein distance between two strings.
 * This distance is a measure of the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.
 *
 * @param {string} s The first string.
 * @param {string} t The second string.
 * @returns {number} The Levenshtein distance between the two strings.
 */
function levenshteinDistance(s, t) {
  // If either string is empty, the distance is the length of the other string.
  if (s.length === 0) return t.length;
  if (t.length === 0) return s.length;

  // Create a 2D array to store the distances between substrings.
  const distances = Array(s.length + 1).fill(null).map(() => Array(t.length + 1).fill(0));

  // Initialize the first row and column of the array.
  for (let i = 0; i <= s.length; i++) {
    distances[i][0] = i;
  }
  for (let j = 0; j <= t.length; j++) {
    distances[0][j] = j;
  }

  // Fill in the rest of the array using dynamic programming.
  for (let i = 1; i <= s.length; i++) {
    for (let j = 1; j <= t.length; j++) {
      const cost = s[i - 1] === t[j - 1]? 0 : 1;
      const mi = Math.min(
        distances[i - 1][j] + 1,
        distances[i][j - 1] + 1,
        distances[i - 1][j - 1] + cost
      );

      // If the current characters in the strings are equal, there is no cost.
      if (cost === 0) {
        distances[i][j] = mi;
      } else {
        // Otherwise, the cost is 1.
        distances[i][j] = mi;

        // Check for Damerau transposition.
        if (i > 1 && j > 1 && s[i - 1] === t[j - 2] && s[i - 2] === t[j - 1]) {
          distances[i][j] = Math.min(distances[i][j], distances[i - 2][j - 2] + cost);
        }
      }
    }
  }

  // The Levenshtein distance is stored in the bottom-right corner of the array.
  return distances[s.length][t.length];
}

module.exports = levenshteinDistance;

This code implements the Levenshtein distance algorithm, which calculates the minimum number of edits (insertions, deletions, or substitutions) needed to transform one string into another.

Here's a breakdown:

1. Initialization:

   • It creates a 2D array d to store the distances between substrings of s and t.
   • It handles edge cases where one or both strings are empty.

2. Base Cases:

   • The first row and column of d are filled with the distances for substrings of length 0.

3. Iteration:

   • The code iterates through the remaining cells of d, calculating the minimum edit distance for each pair of substrings.
   • It considers three possible operations:
     • Insertion: d[i - 1][j] + 1
     • Deletion: d[i][j - 1] + 1
     • Substitution: d[i - 1][j - 1] + cost (where cost is 0 if the characters match, 1 otherwise)

4. Damerau Transposition:

   • The code also includes a special case for transposition (swapping adjacent characters), which can potentially reduce the edit distance.

5. Result:

   • Finally, the function returns the value in d[n][m], which represents the Levenshtein distance between the entire strings s and t.