Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# 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