Typos happen
Someone types mommo. The edit distance — the fewest single-letter inserts, deletes or replacements to turn one word into another — tells you momo is one edit away. It's the dynamic-programming table from Algorithms, now powering a real feature.
The table and the ranking
function editDistance(a, b) {
const dp = Array.from({ length: a.length + 1 }, (_, i) => [i, ...Array(b.length).fill(0)]);
for (let j = 1; j <= b.length; j++) dp[0][j] = j;
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
dp[i][j] = Math.min(
dp[i - 1][j] + 1, // delete
dp[i][j - 1] + 1, // insert
dp[i - 1][j - 1] + (a[i - 1] === b[j - 1] ? 0 : 1), // replace (or keep)
);
}
}
return dp[a.length][b.length];
}
function suggest(word, vocabulary, maxDistance = 2) {
return [...vocabulary.entries()]
.map(([w, count]) => ({ w, count, d: editDistance(word, w) }))
.filter((x) => x.d <= maxDistance)
.sort((a, b) => a.d - b.d || b.count - a.count || (a.w < b.w ? -1 : 1))
.map((x) => x.w);
}