LevenshteinDistance.js

/**
 * @function calculateLevenshteinDp
 * @description A Dynamic Programming based solution for calculation of the Levenshtein Distance.
 * @param {String} x - Word to be converted.
 * @param {String} y - Desired result after operations.
 * @return {Integer} The Levenshtein distance between x and y.
 * @see [Levenshtein_distance](https://en.wikipedia.org/wiki/Levenshtein_distance)
 */

function minimum(a, b, c) {
 if (a < b && a < c) {
 return a
 } else if (b < a && b < c) {
 return b
 } else {
 return c
 }
}

function costOfSubstitution(x, y) {
 return x === y ? 0 : 1
}

// Levenshtein distance between x and y
function calculateLevenshteinDp(x, y) {
 const dp = new Array(x.length + 1)
 for (let i = 0; i < x.length + 1; i++) {
 dp[i] = new Array(y.length + 1)
 }

 for (let i = 0; i < x.length + 1; i++) {
 for (let j = 0; j < y.length + 1; j++) {
 if (i === 0) {
 dp[i][j] = j
 } else if (j === 0) {
 dp[i][j] = i
 } else {
 dp[i][j] = minimum(
 dp[i - 1][j - 1] +
 costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)),
 dp[i - 1][j] + 1,
 dp[i][j - 1] + 1
 )
 }
 }
 }

 return dp[x.length][y.length]
}

export { calculateLevenshteinDp }