Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
deletion distance - being interviewer
"""
input: two strings
output: deletion distance
"""
def deletion_distance_helper(str1, str2, index1, index2):
if str1[index1] == str2[index2]:
deletion_distance_helper(str1, str2, index1 + 1, index2 + 1)
# base case
def deletion_distance(str1, str2):
if str1 == str2:
return 0
using "dog" "frog"
"" "d" "o" "g"
"" "d" "do" "dog"
---------------------------------
"" 0 1 2 3
"f" "f" 1 2 3 4
"r" "fr" 2 3 4 5
"o" "fro" 3 4 3
"g" "frog" 4 ?
dist("f", "d") = min( 1 + dist("", "d"), // delete "d"
1 + dist("f", ""))
dist("f","d") look up table -> left side entry, line 30 , first column
dist("d", "") look up talbe -> upper , line 29, second column
"fro", "do" = min(dist("fr", "d"), dist("fro", "d") + 1, dist("frog","d") + 1)
= dist("fr","d")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.