1. Given two text strings A a2.am of length m and B bib2... bn of length n, you
ID: 3913785 • Letter: 1
Question
1. Given two text strings A a2.am of length m and B bib2... bn of length n, you want to convert A into B with a minimum number of total operations of the following types: . delete a character from A, . insert a character into A, or change some character in A into a new character Examples (1) A-"geek", B "gesek". Optimal result: 1 - by inserting a 's'. (2) A = "Sunday", B-"Saturday". Optimal result. 3. Last three and first characters are same. So we just need to convert "un" into "atur": replace 'n' with r, insert 'a' and 't Design a dynamic programming algorithm. Note that you should first derive the recurrence formula, then write the iterative algorithm to find the minimal number of total operations for conversions, and write the algorithm to display the detailed operations (i.e. delete, insert, or replace)Explanation / Answer
Let us consider two strings(str1,str2):
m: Length of first string
n: Length of second string
Recurrence formula:
minimum_cost(m , n)={ n ,if m = 0
m ,if n = 0
minimumcost(m-1,n-1) ,if str1[m-1]=str2[n-1];
1+min( minimumcost(m , n-1),minimumcost(m-1 , n),minimumcost(m-1 , n-1) ) }
Followings are steps taken two find minimim cost for converting one string to another string using dynamic programming.
1)Declare an arr[m+1][n+1], which arr[i][j] stores minimum cost for converting substring str2(0,j) into str1(0,i).
2)for(i=0.......m)
for(j=0.........n)
(a)if i=0 If first string is empty, only option is to isnert all characters of second string i.e arr[i][j]=n;
(b)if j=0 If second string is empty, the only option is to remove all characters of first string i.e arr[i][j]=m;
(c)if last characters of two strings are same, Ignore last characters and recur for remaining strings.
i.e if(str1[i-1]==atr2[j-1]) arr[i][j]=arr[i-1][j-1];
(e)if the last character is different, consider all possibilities :-
(i) Insert: value for i and j-1 i.e arr[i][j-1]
(ii) Remove: value for i-1 and j i.e arr[i-1][j]
(iii) Replace: value for i-1 and j-1 i.e arr[i-1][j-1]
now take minimum of above three possibilities ,also show which type of operation performed over str2 .
if arr[i][j-1] is minimum ,then operation is inserting a character at jth place in string str2.
if arr[i-1][j] is minimum ,then operation is removing a character at jth place in string str2.
if arr[i-1][j-1] is minimum .then operation is replacing a character at jth place in string str2.
arr[i][j] = ( 1+ min( arr[i][j-1] , arr[i-1][j], arr[i-1][j-1] ));
}
(3)finally return value at arr[m][n] i.e minimum cost for converting str2 into str1.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.