Menu

gitpiper

levenshteinDistance javascript Code Snippet in 2024

stringalgorithmintermediate

Last Updated: 13 February 2024

Calculates the difference between two strings, using the Levenshtein distance algorithm.

  • If either of the two strings has a length of zero, return the length of the other one.
  • Use a for loop to iterate over the letters of the target string and a nested for loop to iterate over the letters of the source string.
  • Calculate the cost of substituting the letters corresponding to i - 1 and j - 1 in the target and source respectively (0 if they are the same, 1 otherwise).
  • Use Math.min() to populate each element in the 2D array with the minimum of the cell above incremented by one, the cell to the left incremented by one or the cell to the top left incremented by the previously calculated cost.
  • Return the last element of the last row of the produced array.
const levenshteinDistance = (s, t) => { if (!s.length) return t.length; if (!t.length) return s.length; const arr = []; for (let i = 0; i <= t.length; i++) { arr[i] = [i]; for (let j = 1; j <= s.length; j++) { arr[i][j] = i === 0 ? j : Math.min( arr[i - 1][j] + 1, arr[i][j - 1] + 1, arr[i - 1][j - 1] + (s[j - 1] === t[i - 1] ? 0 : 1) ); } } return arr[t.length][s.length]; };
levenshteinDistance('duck', 'dark'); // 2

javascript snippet similar to levenshteinDistance For You in February 2024

Subscribe to our Newsletter

Subscribe to get resources directly to your inbox. You won't receive any spam! ✌️

© 2024 GitPiper. All rights reserved

Rackpiper Technology Inc

Company

About UsBlogContact

Subscribe to our Newsletter

Subscribe to get resources directly to your inbox. You won't receive any spam! ✌️