Advertisement
stanevplamen

levenshtein min distance

Sep 22nd, 2022 (edited)
893
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
JavaScript 1.34 KB | Software | 0 0
  1. // Javascript program to
  2. // find minimum numberoperations
  3.  
  4.  
  5. function editDist(str1, str2, m, n)
  6. {
  7.     // If first string is empty, the
  8.     // only option is to insert all
  9.     // characters of second string into first
  10.     if (m == 0) {
  11.         return n ;
  12.     }
  13.  
  14.     // If second string is empty, the only
  15.     // option is to remove all characters
  16.     // of first string
  17.     if (n == 0) {
  18.         return m;
  19.     }
  20.    
  21.     // If last characters of two strings are
  22.     // same, nothing much to do. Ignore last
  23.     // characters and get count for remaining
  24.     // strings.
  25.     if (str1[m - 1] == str2[n - 1]) {
  26.         return editDist(str1, str2, m - 1, n - 1);
  27.     }  
  28.  
  29.     // If last characters are not same, consider all
  30.     // three operations on last character of first
  31.     // string, recursively compute minimum cost for all
  32.     // three operations and take minimum of three
  33.     // values.
  34.     var cI = editDist(str1, str2, m, n - 1); // Insert
  35.     var cR = editDist(str1, str2, m - 1, n); // Remove
  36.     var cC = editDist(str1, str2, m - 1, n - 1); // Replace
  37.  
  38.     var minC = Math.min(cI, cR, cC);
  39.  
  40.     return initialCost + minC;
  41. }
  42.  
  43. // Driver code
  44. let str1 = "developer";
  45. let str2 = "enveloped";
  46.  
  47. var initialCost = 1;
  48.  
  49. debugger;
  50. var cost = editDist(str1, str2, str1.length, str2.length);
  51.  
  52. console.log(cost);
  53.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement