How to resolve the algorithm Levenshtein distance step by step in the Jsish programming language
How to resolve the algorithm Levenshtein distance step by step in the Jsish programming language
Table of Contents
Problem Statement
In information theory and computer science, the Levenshtein distance is a metric for measuring the amount of difference between two sequences (i.e. an edit distance). The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character.
The Levenshtein distance between "kitten" and "sitting" is 3, since the following three edits change one into the other, and there isn't a way to do it with fewer than three edits:
The Levenshtein distance between "rosettacode", "raisethysword" is 8. The distance between two strings is same as that when both strings are reversed.
Implements a Levenshtein distance function, or uses a library function, to show the Levenshtein distance between "kitten" and "sitting".
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Levenshtein distance step by step in the Jsish programming language
Source code in the jsish programming language
/* Levenshtein Distance, in Jsish */
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];
}
provide('levenshtein', 1);
;levenshtein('', '');
;levenshtein('yo', '');
;levenshtein('', 'yo');
;levenshtein('yo', 'yo');
;levenshtein('tier', 'tor');
;levenshtein('saturday', 'sunday');
;levenshtein('mist', 'dist');
;levenshtein('tier', 'tor');
;levenshtein('kitten', 'sitting');
;levenshtein('stop', 'tops');
;levenshtein('rosettacode', 'raisethysword');
;levenshtein('mississippi', 'swiss miss');
/*
=!EXPECTSTART!=
levenshtein('', '') ==> 0
levenshtein('yo', '') ==> 2
levenshtein('', 'yo') ==> 2
levenshtein('yo', 'yo') ==> 0
levenshtein('tier', 'tor') ==> 2
levenshtein('saturday', 'sunday') ==> 3
levenshtein('mist', 'dist') ==> 1
levenshtein('tier', 'tor') ==> 2
levenshtein('kitten', 'sitting') ==> 3
levenshtein('stop', 'tops') ==> 2
levenshtein('rosettacode', 'raisethysword') ==> 8
levenshtein('mississippi', 'swiss miss') ==> 8
=!EXPECTEND!=
*/
You may also check:How to resolve the algorithm Program termination step by step in the PL/I programming language
You may also check:How to resolve the algorithm JSON step by step in the Tcl programming language
You may also check:How to resolve the algorithm Apply a digital filter (direct form II transposed) step by step in the Objeck programming language
You may also check:How to resolve the algorithm Sorting algorithms/Radix sort step by step in the C# programming language
You may also check:How to resolve the algorithm Repeat a string step by step in the TUSCRIPT programming language