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