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:

//Code By Neurox66
function Levenshtein pString1 pString2 
   put 0 into tPosChar1
   repeat for each char tChar1 in pString1 
      add 1 to tPosChar1
      put tPosChar1 into tDistance[tPosChar1][0]  
      put 0 into tPosChar2
      repeat for each char tChar2 in pString2 
         add 1 to tPosChar2
         put tPosChar2 into tDistance[0][tPosChar2]  
         put 1 into tCost
         if tChar1 = tChar2 then 
            put 0 into tCost 
         end if
         put min((tDistance[tPosChar1-1][tPosChar2] + 1),(tDistance[tPosChar1][tPosChar2-1] + 1),(tDistance[tPosChar1-1][tPosChar2-1] + tCost)) into tDistance[tPosChar1][tPosChar2] 
      end repeat  
   end repeat  
   return tDistance[tPosChar1][tPosChar2]  
end Levenshtein


put Levenshtein("kitten","sitting") 
put Levenshtein("rosettacode","raisethysword")