Anonymous user
User talk:Ledrug: Difference between revisions
→Levenshtein distance C code
(Levenshtein distance C code) |
|||
Line 2:
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? --[[User:Mwn3d|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.
| |||