Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Dynamic programming
def main():
result = edit_distance("fox", "fab")
print(result)
def edit_distance(str1, str2):
len1 = len(str1)
len2 = len(str2)
maxtrix = [[i for j in range(len2 +1)] for i in range(len1 + 1)]
maxtrix[0] = [i for i in range(len1 + 1)]
for i in range(1, len1):
for j in range(1, len2):
if str1[i-1] == str2[j-1]:
maxtrix[i][j] = maxtrix[i-1][j-1]
else:
maxtrix[i][j] = min(maxtrix[i][j-1] + 1, maxtrix[i-1][j] + 1, maxtrix[i-1][j-1] + 1)
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.