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

Question

contestada

Respuesta :

sandlee09 sandlee09 · Answer 1 · 2021-04-18T17:26:52+02:00

Answer:

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]