Skip to content

Instantly share code, notes, and snippets.

@isseu
Created November 10, 2015 23:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save isseu/edbcefb70b6432e8ec00 to your computer and use it in GitHub Desktop.
Save isseu/edbcefb70b6432e8ec00 to your computer and use it in GitHub Desktop.
# Edit-Distance algorithm
def edit_distance_alg(string1, string2)
lenString1 = string1.length
lenString2 = string2.length
if([lenString1, lenString2].min == 0)
return [lenString1, lenString2].max
end
return [
edit_distance_alg(string1[0..-2], string2) + 1,
edit_distance_alg(string1, string2[0..-2]) + 1,
edit_distance_alg(string1[0..-2], string2[0..-2]) + ((string1[-1] != string2[-1]) ? 1 : 0)
].min
end
def check_K_palindrome(k, string)
puts edit_distance_alg(string, string.reverse)
return edit_distance_alg(string, string.reverse) <= k * 2
end
puts check_K_palindrome(1, "oloa")
puts edit_distance_alg("holab", "aaolac")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment