Levenshtein distance
What it is and why you might need it

General description

The Levenshtein distance between two strings is the minimum number of insert, delete, and replace operations to convert the first string into the second. This can be useful to check spelling or give alternative word suggestions in a search. Let's discover how to implement it.

Code example

Let's jump right into it. The following code example shows the documented source code of a Levenshtein distance calculation.

function levenshteinDistance(string1, string2) {
	// first, construct the inner array
	const distance = [];

	for (let i = 0; i < string2.length + 1; i++) {
		const row = [];

		// fill the first row
		for (let j = 0; j < string1.length + 1; j++) {
			row.push(j);
		}

		// the first entry will be always incrementing
		row[0] = i;
		distance.push(row);
	}

	// construct the distances for each element
	// start at index 1
	for (let i = 1; i < string2.length + 1; i++) {
		for (let j = 1; j < string1.length + 1; j++) {
			//  check if the current element in both strings match
			if (string1[i - 1] === string2[j - 1]) {
				// same chars - no more edits
				distance[i][j] = distance[i - 1][j - 1];
			} else {
				// take the min from the outer
				distance[i][j] =
					1 +
					Math.min(
						distance[i - 1][j],
						distance[i][j - 1],
						distance[i - 1][j - 1],
					);
			}
		}
	}
	return distance[string2.length][string1.length];
}

So, we know that the Levenshtein distance basically tells us about the "difference" of two separate strings. For what might this be useful? One example could be the suggestion of similar words in a search component of your application. The following interactive example shows a possible implementation. You can use the two input fields to test out the Levenshtein distance for several different words in the list, like:
drums, drummer, trumpets, php, javascript
and more...

Complexity analysis

• The time complexity of this algorithm is O(nm), as we iterate over each letter for both strings in nested loops while each step has a constant computation time
• the space complexity is O(nm) as well

I hope this little example shows you where you could use this algorithm. Maybe your next project can benefit from it