Showing the result of Levenshtein Distance -

given 2 strings (s1, s2), levenshtein distance minimum number of operations needed change s1 s2 or vice versa.

i want show result of changing s1 s2. example, changing sunday saturday needs 3 operations. need show s++u+day. "+" each operations needed.

here javascript snippet returns want. if familiar dynamic programming algorithm should able follow code. string operations/manipulation of return string r , handling of min/curmin what's changed original version.

function edits(t, s) {     var r = "";     if (s === t) {         return s;     }     var n = s.length, m = t.length;     if (n === 0 || m === 0) {         return "+".repeat(n + m);     }     var x, y, a, b, c, min = 0;     var p = new array(n);     (y = 0; y < n;)         p[y] = ++y;     (x = 0; x < m; x++) {         var e = t.charcodeat(x);         c = x;         b = x + 1;         var currmin = min;         min = n + 1;         (y = 0; y < n; y++) {             = p[y];             if (a < c || b < c) {                 b = (a > b ? b + 1 : + 1);             }             else {                 if (e !== s.charcodeat(y)) {                     b = c + 1;                 }                 else {                     b = c;                 }             }             if (b < min) {                 min = b;             }             p[y] = b;             c = a;         }         if (min > currmin) {             r += "+";         }         else {             r += t[x];         }     }     return r; } 

edit: implementation above version optimized speed , space might harder read. implemetation below modified version of js version wikipedia , should easier follow.

function geteditdistance(a, b) {     if(a.length === 0) return "+".repeat(b.length);     if(b.length === 0) return "+".repeat(a.length);      var matrix = [];      // increment along first column of each row     var i;     for(i = 0; <= b.length; i++){         matrix[i] = [i];     }      // increment each column in first row     var j;     for(j = 0; j <= a.length; j++){         matrix[0][j] = j;     }      var r = "", min = 0;;      // fill in rest of matrix     for(i = 1; <= b.length; i++){          var currmin = min;         min = a.length + 1;          for(j = 1; j <= a.length; j++){              if(b.charat(i-1) == a.charat(j-1)){                 matrix[i][j] = matrix[i-1][j-1];             } else {                 matrix[i][j] = math.min(matrix[i-1][j-1] + 1, // substitution                     math.min(matrix[i][j-1] + 1, // insertion                         matrix[i-1][j] + 1)); // deletion             }              if (matrix[i][j] < min) {                 min = matrix[i][j];             }         }          if (min > currmin) {             r += "+";         }         else {             r += b[i-1];         }     }     return r; } 

edit2: added explanation of algorithm , example output

below levenshtein matrix input strings "kitten" , "sitting". changed in original algorithm added check if current rows minimum value larger previous rows minimum, , if is, there edit in current row , adding "+". if not , " edit cost" current row same previous. there no edit necessary , add current character result string. can follow algorithm row row in image (starting @ row 1, , column 1)

examples:

> geteditdistance("kitten", "sitting"); '+itt+n+' > geteditdistance("sunday", "saturday"); 's++u+day'