Write a recursive function that computes the edit distance between two strings. Use the following algorithm:Let s and t be the stringsIf the length of s is 0 thenReturn the length of tElse if the length of t is 0 thenReturn the length of sElseSet cost to 0If the last character in s does not equal the last character in t then Set cost to 1Set d1 equal to the edit distance between all characters except the last one in s, and all characters in t, plus 1Set d2 equal to the edit distance between all characters in s, and all characters except the last one in t, plus 1Set d3 equal to the edit distance between all characters except the last one in s, and all characters except the last one in t, plus costReturn the minimum of d1, d2 and d3
Question
Write a recursive function that computes the edit distance between two strings. Use the following algorithm:Let s and t be the stringsIf the length of s is 0 thenReturn the length of tElse if the length of t is 0 thenReturn the length of sElseSet cost to 0If the last character in s does not equal the last character in t then Set cost to 1Set d1 equal to the edit distance between all characters except the last one in s, and all characters in t, plus 1Set d2 equal to the edit distance between all characters in s, and all characters except the last one in t, plus 1Set d3 equal to the edit distance between all characters except the last one in s, and all characters except the last one in t, plus costReturn the minimum of d1, d2 and d3
Solution
Sure, here is the Python code for the recursive function that computes the edit distance between two strings:
def edit_distance(s, t):
if len(s) == 0:
return len(t)
elif len(t) == 0:
return len(s)
else:
cost = 0
if s[-1] != t[-1]:
cost = 1
d1 = edit_distance(s[:-1], t) + 1
d2 = edit_distance(s, t[:-1]) + 1
d3 = edit_distance(s[:-1], t[:-1]) + cost
return min(d1, d2, d3)
This function works by recursively comparing the last characters of the strings s and t, and computing the minimum cost of inserting, deleting, or substituting a character. The base cases are when one of the strings is empty, in which case the edit distance is simply the length of the other string.
Similar Questions
Take the input string and words from the user. Find an efficient algorithm to find the smallest distance (measured in number of words) between any two given words in that string. If no such words are present in that string it should return "None".For example, given a text content of "dog cat hello cat dog dog hello cat world" and words are "hello" and "world" it should return 1 because there's only one word "cat" in between the two words.Sample Test CasesTest Case 1:Expected Output:Enter·the·text:·dog cat hello cat dog dog hello cat worldEnter·a·word·from·the·given·text:·helloEnter·another·word·from·the·given·text:·world1Test Case 2:Expected Output:Enter·the·text:·python eats another pythonEnter·a·word·from·the·given·text:·pythonEnter·another·word·from·the·given·text:·animalNone
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.For example, "ace" is a subsequence of "abcde".A common subsequence of two strings is a subsequence that is common to both strings. Example 1:Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.
program must accept two string values S1 (may contain space) and S2 (one word) as the input. The words in S1 are sorted lexicographically and separated by exactly one space. The program must insert the the string S2 in S1 such that all the words in the modified S1 are also in sorted order.Note: The string values contain only lower case alphabetsBoundary Condition(s):1 <= Length of S1 <= 10001 <= Length of S2 <= 100Input Format:The first line contains S1.The second line contains S2.Output Format:The first line contains the modified S1.Example Input/Output 1:Input:abacus ball dog hat mind zebrainkOutput:abacus ball dog hat ink mind zebraExample Input/Output 2:Input:captain celbrate cricketcrackerOutput:captain celbrate cracker cricket
The program needs to compare two given strings lexicographically and output the difference between them. (using compareTo() function)If the first string is greater than the second string, it should output a positive value, If they are equal it should output 0If the first string is less than the second string, it should output a negative valueInput format :The first line of the input consists of a string.The second line of the input consists of a string.Output format :The output should display the following constraintsNote :If (string1 > string2), it returns a positive value (the difference between the characters).If both the strings are equal lexicographically, i.e., (string1 == string2), it returns 0.If (string1 < string2), it returns a negative value (the difference between the characters).Sample test cases :Input 1 :harryharryOutput 1 :0Input 2 :helloworldOutput 2 :-15Input 3 :tiger lionOutput 3 :8
You are given two strings, A and B. Answer, what is the smallest number of operations you need totransform A to B?Operations are:Delete one letter from one of stringsInsert one letter into one of stringsReplace one of letters from one of strings with another letterInputT - number of test casesFor each test case:String AString BBoth strings will contain only uppercase characters and they won't be longer than 2000 characters. There will be 10 test cases in data set.OutputFor each test case, one line, minimum number of operations.ExampleInput:1FOODMONEYOutput:4
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.