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

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

venereology answered 1 year ago

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.

(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...

Implement a function that returns the maximum number in a given unsorted linked list. For example,...

Implement a function that returns the maximum number in a given unsorted linked list. For example, there is a linked list 3->5->1->10->9. The printMax() function in max.c should return the maximum number in the linked list, namely 10 in the example. 1. Implement max.c with the completed printMax() function. 2. Provide an explanation for your solution #include <stdio.h> typedef struct node { int value; struct node *next; } node; int printMax(node *first) { // Your implementation return 0; } int...

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.

Solving Problems Using Recursion (Python): To solve the problem, you have to use recursion and cannot...

Solving Problems Using Recursion (Python): To solve the problem, you have to use recursion and cannot use for or while loops to solve the problems as well as not using global variables. 1. Create a function that takes a positive integer and returns it with neighboring digits removed. Do not convert the integer to a list. Ex. Input = [5555537777721] Output = [53721]

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.