freeCodeCamp/curriculum/challenges/ukrainian/10-coding-interview-prep/rosetta-code/levenshtein-distance.md

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
5e4ce2eaac708cc68c1df260	Відстань Левенштейна	5	385264	levenshtein-distance

--description--

У інформаційній теорії та комп'ютерних науках відстань Левенштейна — це [метрика](https://en.wikipedia.org/wiki/string metric), яка вимірює відмінність між двома послідовностями (тобто [відстань редагування](https://en.wikipedia.org/wiki/edit distance)). Відстань Левенштейна між двома рядками визначається як мінімальна кількість операцій вставки, видалення або заміни, необхідних для перетворення одного рядка в інший.

Наприклад:

Відстань Левенштейна між "kitten" і "sitting" складають 3, оскільки неможливо перетворити одне слово в інше за меншу кількість операцій:

• kitten sitten (заміна 'k' на 's')
• sitten sittin (заміна 'e' на 'i')
• sittin sitting (вставити 'g' в кінці).

Відстань Левенштейна між "rosettacode" та "raisethysword" складає 8.

Якщо рядки поміняти місцями, відстань між ними не зміниться.

--instructions--

Напишіть функцію, яка повертає відстань Левенштейна між двома рядками, вказаними як параметри.

--hints--

levenshtein має бути функцією.

assert(typeof levenshtein == 'function');

levenshtein("mist", "dist") має повернути число.

assert(typeof levenshtein('mist', 'dist') == 'number');

levenshtein("mist", "dist") має повернути 1.

assert.equal(levenshtein('mist', 'dist'), 1);

levenshtein("tier", "tor") має повернути 2.

assert.equal(levenshtein('tier', 'tor'), 2);

levenshtein("kitten", "sitting") має повернути 3.

assert.equal(levenshtein('kitten', 'sitting'), 3);

levenshtein("stop", "tops") має повернути 2.

assert.equal(levenshtein('stop', 'tops'), 2);

levenshtein("rosettacode", "raisethysword") має повернути 8.

assert.equal(levenshtein('rosettacode', 'raisethysword'), 8);

levenshtein("mississippi", "swiss miss") має повернути 8.

assert.equal(levenshtein('mississippi', 'swiss miss'), 8);

--seed--

--seed-contents--

function levenshtein(a, b) {

}

--solutions--

function levenshtein(a, b) {
  var t = [], u, i, j, m = a.length, n = b.length;
  if (!m) { return n; }
  if (!n) { return m; }
  for (j = 0; j <= n; j++) { t[j] = j; }
  for (i = 1; i <= m; i++) {
    for (u = [i], j = 1; j <= n; j++) {
      u[j] = a[i - 1] === b[j - 1] ? t[j - 1] : Math.min(t[j - 1], t[j], u[j - 1]) + 1;
    } t = u;
  } return u[n];
}