In: Computer Science
Python: Implement edit_diff using recursion, which is a diff function that returns the minimum number of edit operations needed to transform the start word into the goal word.
There are three kinds of edit operations:
Add a letter to start,
Remove a letter from start,
Substitute a letter in start for another.
Each edit operation contributes 1 to the difference between two words.
>>> big_limit = 10
>>> edit_diff("roses", "arose", big_limit) # roses -> aroses -> arose
2
>>> edit_diff("tesng", "testing", big_limit) # tesng -> testng -> testing
2
>>> edit_diff("rlogcul", "logical", big_limit) # rlogcul -> logcul -> logicul -> logical
3
If the number of edits required is greater than limit, then edit_diff should return any number larger than limit and should minimize the amount of computation needed to do so. A function that may be helpful is provided below:
def swap_diff(start, goal, limit):
"""A diff function that computes the edit distance from START to GOAL."""
if ________:
elif ________:
else:
add_diff = ... # Fill in these lines
remove_diff = ...
substitute_diff = ...
# BEGIN
add_diff=0
remove_diff=0
substitute_diff=0
def swap_Diff(str1, str2, limit):
m=len(str1)
n=len(str2)
if m==0:
return n
if n==0:
return m
if str1[m-1]==str2[n-1]:
return edit_Diff(str1,str2,m-1,n-1)
add = edit_Diff(str1, str2, m, n-1)
Remove = edit_Diff(str1, str2, m-1, n)
Substitue = edit_Diff(str1, str2, m-1, n-1)
minm = min(Ins, Rmv. Rplc)
if minm==add:
add_diff++
elif minm==Remove:
remove_diff++
else:
substitue_diff++
return 1 + minm