Question

In: Computer Science

Python: Implement edit_diff using recursion, which is a diff function that returns the minimum number of...

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

Solutions

Expert Solution

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


Related Solutions

In python I want to create a function that takes in a linked list. Using recursion...
In python I want to create a function that takes in a linked list. Using recursion only, I want to check if the linked list is sorted. How do i do this?
Python Implement function noVowel() that takes a string s as input and returns True if no...
Python Implement function noVowel() that takes a string s as input and returns True if no char- acter in s is a vowel, and False otherwise (i.e., some character in s is a vowel). >>> noVowel('crypt') True >>> noVowel('cwm') True >>> noVowel('car') False
Write a program in python that implements quicksort, first using recursion and then without recursion.
Write a program in python that implements quicksort, first using recursion and then without recursion.
(Python) Implement a function to compute a sum that can compute sum for an arbitrary number...
(Python) Implement a function to compute a sum that can compute sum for an arbitrary number of input integers or float numbers. In other words, calls like this should all work: flexible_sum(x1, x2) # sum of two integer or float numbers or strings x1 and x2 flexible_sum(x1, x2, x3) # sum of 3 input parameters and can also handle a single input parameter, returning it unchanged and with the same type, i.e.:   flexible_sum(1) returns 1 and can accept an arbitrary...
USING PYTHON, write a function that takes a list of integers as input and returns a...
USING PYTHON, write a function that takes a list of integers as input and returns a list with only the even numbers in descending order (Largest to smallest) Example: Input list: [1,6,3,8,2,5] List returned: [8, 6, 2]. DO NOT use any special or built in functions like append, reverse etc.
Use Python Write a function that takes a mobile phone number as a string and returns...
Use Python Write a function that takes a mobile phone number as a string and returns a Boolean value to indicate if it is a valid number or not according to the following rules of a provider: * all numbers must be 9 or 10 digits in length; * all numbers must contain at least 4 different digits; * the sum of all the digits must be equal to the last two digits of the number. For example '045502226' is...
On Python Write a function that accepts a relative file path as parameter and returns number...
On Python Write a function that accepts a relative file path as parameter and returns number of non-empty lines in the file. Test your function with the provided sample file studentdata.txt.
Write a PYTHON function CommonLetters(mystring) that takes mystring as input and returns the number of letters...
Write a PYTHON function CommonLetters(mystring) that takes mystring as input and returns the number of letters in mystring that also occur in the string ‘Python’. Using above function, write a program that repeatedly prompts the user for a string and then prints the number of letters in the string that are also in string ‘Python’. The program terminates when the user types an empty string.
Write a python code to Design and implement a function with no input parameter which reads...
Write a python code to Design and implement a function with no input parameter which reads a number from input (like 123). Only non-decimal numbers are valid (floating points are not valid). The number entered by the user should not be divisible by 10 and if the user enters a number that is divisible by 10 (like 560), it is considered invalid and the application should keep asking until the user enters a valid input. Once the user enters a...
/*Use recursion in the function: void getDigit( int num) /* Try this program and implement the...
/*Use recursion in the function: void getDigit( int num) /* Try this program and implement the function void getDigit( intnum) so that it displays the digits in a given number. For example, the number, 1234 consist of 1, 2, 3 and 4. This is an exercise to demonstate the use of a recursive function and the use of recusrion in C++ */ #include #include using namespace std; int main() {      int num;      cout <<"Enter an integer: ";     ...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT