Minimum Cost to Make Two Strings Identical
Given two strings string1 and string2 find the minimum cost required to make the given two strings identical. We can delete characters from both the strings. The cost of deleting a character from string1 is costX and string2 is costY. The cost of removing any characters from the same string is the same. Like, removing any
Input:
The first line contains integers costX and costY.
The second line contains the two strings X and Y.
Output:
Print the total cost to make the two strings
equal for each test case in a new line.
Constraints:
1<= length of strings X and Y <=1000
1<= costX, costY <=1000
Explanation of Example:
Input:
1
10 20
"acba" "acdb"
Output:
30
Explanation:
The similar strings would be "acb".
So need to remove one from string1 and one from string2
costing total of 30.
The problem can be solved recursively,
Let,
Let us consider, what can be cases that can arrive for F(i,j) where 0 <= i<n && 0 <= j<m
Case 1.
string1[i]==string2[j] that is indexed characters are similar
In such a case, we don't need any additional cost to make strings similar, the cost will be similar to sub-problem of size i-1, j-1. This can be recursively written as
Case 2.
string1[i]!=string2[j] that is indexed characters are not similar.
In such a case we need to invest,
This can be recursively written as,
This can be recursively written as,
This can be recursively written as, Finally, we would take minimum out of this three cases.
So here goes the problem structure,
Now the above recursion will create many overlapping subproblems and hence we need two converts it into DP.
Converting into DP
C++ Implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer