User talk:Ledrug
Levenshtein distance C code
I Just noticed that you posted a recursive C solution for Levenshtein distance. Could you maybe explain (here or in/near the example) what the variables mean in that solution? I tried to come up with a recursive solution in Java myself, but it didn't work out so well. If at all possible could you maybe just give some pseudocode for the recursive algorithm? --Mwn3d 20:25, 20 June 2011 (UTC)
- The recursion function has 4 parameters: s, string 1; ls: length of s; t: string 2; lt length of t. Basically, <lang>function levenschtein(s, t)
if length(s) = 0: return length(t) if length(t) = 0: return length(s) if s[0] = t[0] : return levelschtein(s[1 .. end], t[1 .. end])
len1 := levelschtein(s, t[1 .. end]) + 1 len2 := levelschtein(s[1 .. end], t) + 1 len3 := levelschtein(s[1 .. end], t[1 .. end]) + 1 return min(len1, len2, len3)
</lang>where s[0] meaning first char in string s; s[1 .. end] meaning s without first char.