detect-typo.js 1.4 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546
  1. "use strict";
  2. Object.defineProperty(exports, "__esModule", {
  3. value: true
  4. });
  5. exports.detectTypo = detectTypo;
  6. // the minimum number of operations required to convert string a to string b.
  7. function minDistance(a, b, threshold) {
  8. const m = a.length;
  9. const n = b.length;
  10. if (m < n) {
  11. return minDistance(b, a, threshold);
  12. }
  13. if (n === 0) {
  14. return m;
  15. }
  16. let previousRow = Array.from({
  17. length: n + 1
  18. }, (_, i)=>i);
  19. for(let i1 = 0; i1 < m; i1++){
  20. const s1 = a[i1];
  21. let currentRow = [
  22. i1 + 1
  23. ];
  24. for(let j = 0; j < n; j++){
  25. const s2 = b[j];
  26. const insertions = previousRow[j + 1] + 1;
  27. const deletions = currentRow[j] + 1;
  28. const substitutions = previousRow[j] + Number(s1 !== s2);
  29. currentRow.push(Math.min(insertions, deletions, substitutions));
  30. }
  31. previousRow = currentRow;
  32. }
  33. return previousRow[previousRow.length - 1];
  34. }
  35. function detectTypo(input, options, threshold = 2) {
  36. const potentialTypos = options.map((o)=>({
  37. option: o,
  38. distance: minDistance(o, input, threshold)
  39. })).filter(({ distance })=>distance <= threshold && distance > 0).sort((a, b)=>a.distance - b.distance);
  40. if (potentialTypos.length) {
  41. return potentialTypos[0].option;
  42. }
  43. return null;
  44. }
  45. //# sourceMappingURL=detect-typo.js.map