Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for [old] String Conversion by mortonfox
"use strict";
// Adapted from https://en.wikipedia.org/wiki/Levenshtein_distance
function stepsToConvert(line1, line2) {
// degenerate cases
if (line1 == line2) return 0;
if (line1.length == 0) return line2.length;
if (line2.length == 0) return line1.length;
// create two work vectors of integer distances
var v0 = [];
var v1 = [];
// initialize v0 (the previous row of distances)
// this row is A[0][i]: edit distance for an empty s
// the distance is just the number of characters to delete from t
for (var i = 0; i < line2.length + 1; i++) v0[i] = i;
for (var i = 0; i < line1.length; ++i) {
// calculate v1 (current row distances) from the previous row v0
// first element of v1 is A[i+1][0]
// edit distance is delete (i+1) chars from s to match empty t
v1[0] = i + 1;
// use formula to fill in the rest of the row
for (var j = 0; j < line2.length; j++) {
var cost = (line1[i] == line2[j]) ? 0 : 1;
v1[j + 1] = Math.min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
}
// copy v1 (current row) to v0 (previous row) for next iteration
v0 = v1;
v1 = [];
}
return v0[line2.length];
}
var assert = require('assert');
if (!global.is_checking) {
assert.equal(stepsToConvert('line1', 'line1'), 0, "eq")
assert.equal(stepsToConvert('line1', 'line2'), 1, "2")
assert.equal(stepsToConvert('line', 'line2'), 1, "none to 2")
assert.equal(stepsToConvert('ine', 'line2'), 2, "need two more")
assert.equal(stepsToConvert('line1', '1enil'), 4, "everything is opposite")
assert.equal(stepsToConvert('', ''), 0, "two empty")
assert.equal(stepsToConvert('l', ''), 1, "one side")
assert.equal(stepsToConvert('', 'l'), 1, "another side")
console.log("You are good to go!");
}
Oct. 8, 2016