User talk:Ledrug: Difference between revisions
Content added Content deleted
m (sign) |
|||
| Line 12: | Line 12: | ||
len3 := levelschtein(s[1 .. end], t[1 .. end]) + 1 |
len3 := levelschtein(s[1 .. end], t[1 .. end]) + 1 |
||
return min(len1, len2, len3) |
return min(len1, len2, len3) |
||
</lang>where s[0] meaning first char in string s; s[1 .. end] meaning s without first char. |
</lang>where s[0] meaning first char in string s; s[1 .. end] meaning s without first char. (heh this reads just like the C code. I suck at pseudo code.) --[[User:Ledrug|Ledrug]] 20:39, 20 June 2011 (UTC) |
||
Revision as of 20:39, 20 June 2011
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. (heh this reads just like the C code. I suck at pseudo code.) --Ledrug 20:39, 20 June 2011 (UTC)