Question

Write a recursive method named editDistance that accepts string parameters s1 and s2 and returns the "edit distance" between the two strings as an integer. Edit distance (also called Levenshtein distance) is defined as the minimum number of "changes" required to get from s1 to s2 or vice versa. A "change" can be defined as a) inserting a character, b) deleting a character, or c) changing a character to a different character. Call Value Returned editDistance("driving", "diving") 1 editDistance("debate", "irate") 3 editDistance("football", "cookies") 6

Answer 1

Step-by-step explanation:

The following code takes in the two parameters s1 and s2 and returns the Levenshtein distance of the two strings passed.

def editDistance(s1, s2):

m = len(s1) + 1

n = len(s2) + 1

arr = {}

for x in range(m):

arr[x, 0] = x

for y in range(n):

arr[0, y] = y

for x in range(1, m):

for y in range(1, n):

proc = 0 if s1[x - 1] == s2[y - 1] else 1

arr[x, y] = min(arr[x, y - 1] + 1, arr[x - 1, y] + 1, arr[x - 1, y - 1] + proc)

return arr[x, y]