Расстояние Левенштейна

1function levenshtein(a: string, b: string): number {
2  const m = a.length, n = b.length
3  // d[i][j] — расстояние первых i символов a до первых j символов b
4  const d: number[][] = Array.from({ length: m + 1 }, () =>
5    new Array(n + 1).fill(0),
6  )
7 
8  for (let i = 0; i <= m; i++) d[i][0] = i // удалить всё
9  for (let j = 0; j <= n; j++) d[0][j] = j // вставить всё
10 
11  for (let i = 1; i <= m; i++) {
12    for (let j = 1; j <= n; j++) {
13      const cost = a[i - 1] === b[j - 1] ? 0 : 1
14      d[i][j] = Math.min(
15        d[i - 1][j] + 1,      // удалить
16        d[i][j - 1] + 1,      // вставить
17        d[i - 1][j - 1] + cost, // заменить/совпало
18      )
19    }
20  }
21 
22  return d[m][n]
23}