Skip to content

Instantly share code, notes, and snippets.

@hammeiam
Last active March 9, 2021 19:50
Show Gist options
  • Save hammeiam/e1e391d6ecb36441fad9a49bbd58a8d4 to your computer and use it in GitHub Desktop.
Save hammeiam/e1e391d6ecb36441fad9a49bbd58a8d4 to your computer and use it in GitHub Desktop.
Simple Find Closest Word
// You can modify these
const wordsToCheck = ["Apple", "red delisous", "orangg", "rgapefruit"];
const dictionary = ["apple", "banana", "orange", "grapefruit", "red delicious"];
// Don't modify below here
const ALPHABET = "qwertyuiopasdfghjklzxcvbnm1234567890_ ".split("").sort();
const BASE_ALPHABET_HASH = ALPHABET.reduce((acc, x) => ({[x]: 0, ...acc}), {});
const DICTIONARY_HASHES = dictionary.map((w) => buildFreqHash(cleanStr(w)));
// clean a string
function cleanStr(s) {
return s.replace(/[\s_]+/g, " ").toLowerCase();
}
const distance = (a, b) => a.reduce((acc, v, i) => acc + Math.abs(v - b[i]), 0);
// build a character frequency hash from a string in alphabetical order
function buildFreqHash(s) {
const h = {...BASE_ALPHABET_HASH};
s.split("").forEach((l) => h[l]++);
return ALPHABET.map((l) => h[l]);
}
// find the closest word based on the fewest edits
function closestWord(word) {
const hash = buildFreqHash(cleanStr(word));
const distances = DICTIONARY_HASHES.map((h) => distance(hash, h));
return dictionary[
distances.reduce(
(closestIdx, d, i) => (distances[closestIdx] < d ? closestIdx : i),
0
)
];
}
// This runs the code
wordsToCheck.forEach((w) =>
console.log(`'${closestWord(w)}' is closest to '${w}'`)
);
/**
* Output:
* 'apple' is closest to 'Apple'
* 'red delicious' is closest to 'red delisous'
* 'orange' is closest to 'orangg'
* 'grapefruit' is closest to 'rgapefruit'
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment