One Pager Cheat Sheet

• The Edit Distance between two strings is calculated by finding the minimum number of insertion, deletion, and substitution transformations required to turn the first string into the second.
• The Levenshtein edit distance is a mathematical formula developed by Vladimir Levenshtein in 1965, which measures the number of edits required to convert one string to another.
• The Levenshtein distance between two strings a and b can be calculated using an indicator function and a mathematical formula.
• The cost of transformation between two strings is measured by the distance between them, being 0 for no difference and increasing for any differences.
• The running distance between two strings should be incremented by 1 if their characters at the same index are different.
• The Levenshtein edit distance can be calculated using an array matrix to track the n^2 possible transformations.
• The algorithm uses a table to accumulate costs in order to find the minimum cumulative transformation distance between two strings.
• We need to move from the * indicated cell to the right, adding up the cost of 1 at each intersection as we go, and selecting the minimum of the three options at every step.
• By comparing the letters e and t first, and noting that e and e have no cost, we can determine the optimal cost of 1 + 1 for the first 2 columns.
• We arrive at 3 (2 + 1) by s, the bottom-right corner.
• The 2x2 matrix with values 1 through 4 results in the best score when diagonally mirrored.
• Our Final Solution has O(m*n) time and space complexity.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function getEditDistance(a, b) {

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

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

​

  var matrix = [];

​

  // increment along the first column of each row

  var i;

  for (i = 0; i <= b.length; i++) {

    matrix[i] = [i];

  }

​

  // increment each column in the first row

  var j;

  for (j = 0; j <= a.length; j++) {

    matrix[0][j] = j;

  }

​

  // Fill in the rest of the matrix

  for (i = 1; i <= b.length; i++) {

    for (j = 1; j <= a.length; j++) {

      if (b.charAt(i - 1) == a.charAt(j - 1)) {

        matrix[i][j] = matrix[i - 1][j - 1];

      } else {

        matrix[i][j] = Math.min(

          matrix[i - 1][j - 1] + 1, // substitution

          Math.min(

            matrix[i][j - 1] + 1, // insertion

            matrix[i - 1][j] + 1

          )

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.