Edit distance python program

Sample/Example:

import math

def edistance(A, B):

pass

def weighted_edistance(A, B, wdel, wins, wsub):

pass

def edistance_substring(A, B):

pass

if __name__ == "__main__":

# should print 3

print(edistance("good", "bad"))

# should print 7

print(weighted_edistance("good", "bad", 1, 2, 5))

Input: strings A and B Output: the smallest number of operations (insertion, deletion, and substitution) needed to transform A to B. This number is usually called the edit distance. For example, the edit distance between "good" and "bad" is three: good -> ood -> bod -> bad. We will approach this problem using dynamic programming. Let |A| = n and (B) = = m. We will fill a (n + 1) (m + 1) table D such that D[i][j] will be the edit distance between A[: i] and B[: j]. We will derive a recurrence to compute D[i][j]. Consider two cases: Case Ai 1] = B[j 1]. Then we can focus on beginnigns of both strings, so D[i][j] = D[i 1][j 1]. Case Ai 1] # B[j 1]. Since we want ultimately make the stings equal, there are three options We delete A[i 1]. The remaining number of operations is D[i 1][j] We delete B[j 1]. The remaining number of operations is D[i][j 1] We substitute A[i 1] for B[j 1]. The remaining number of operations is D[i 1][j 1]. . Therefore, in this case D[i][j] = 1+ min(D[i 1][j], D[i][j 1], D[i 1] [j 1]). Part 1. Write a function edistance(A, B) using the above recurrence. Part 2. Write a function weighted_edistance(A, B, wdel, wins, wsub) that computes the minimal total weight of the operations to make A from B if wdel, wins, wsub are positive integer weights of deletion, insertion, and substitution, respectively. For example, if wdel = wins = 1 and wsub = 3, the weighted distance between good and bad becomes 5: good ->ood -> od -> d -> ad -> bad. Part 3. Write a function edistance_substring(A, B) that returns the smallest edit distance between a substring of A (that is, a string of the from Ai : j]) and B. In other words, it is allowed to delete some symbols at the beginning and at the end of A for free. For example, if A = good and B = bad, then the output should be 2, because one can transform ood into bad with two subtitutions, and at least two operations are necessary because the letters b and a are not present in A. The complexity of all these functions should be O(|A||Bl), so |A| = |B| = 200 should be fast