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,
N = length of string1 M = length of string1 F(n,m) = minimum cost to make two strings similarLet 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
n = string1 length m = string2 length str1 = string1 str2 = string2 1) Declare int dp[n+1][m+1]; 2) Base case for i=0 to n dp[i][0]=i*costX; for j=0 to m dp[0][j]=j*costY; 3) Fill the DP for i=1 to n for j=1 to m //first case when str1[i-1]==str2[j-1] dp[i][j]=dp[i-1][j-1]; if(str1[i-1]!=str2[j-1]) dp[i][j]+=costX+costY; dp[i][j]=min(dp[i][j],min(dp[i-1][j]+costX,dp[i][j-1]+costY)); end if end for end for 4) return dp[n][m];C++ Implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer