Question
Minimum Cost to Match Strings
You are given two strings s1 and s2. In one operation, you may delete any character from either string, paying a cost equal to its ASCII value of that character.
Your task is to determine the minimum total ASCII cost of deletions required to make the two strings equal.
Output the minimum cost.
Input
First line will contain a string s1.
Second line will contain a string s2.
Second line will contain a string s2.
Output
Print the lowest ASCII sum of deleted characters to make two strings equal.
Example
Input:
sea
eat
Output:
231
Explanation:
Deleting "s" from "sea" adds the ASCII value of "s" (115) to the cost.
Deleting "t" from "eat" adds 116 to the cost.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum cost possible to achieve this.
Input:
delete
leet
Output:
403
Explanation:
Deleting "dee" from "delete" to turn the string into "let",
adds 100[d] + 101[e] + 101[e] to the cost.
Deleting "e" from "leet" adds 101[e] to the cost.
At the end, both strings are equal to "let", and the cost is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get costs of 433 or 417, which are higher.
sea
eat
Output:
231
Explanation:
Deleting "s" from "sea" adds the ASCII value of "s" (115) to the cost.
Deleting "t" from "eat" adds 116 to the cost.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum cost possible to achieve this.
Input:
delete
leet
Output:
403
Explanation:
Deleting "dee" from "delete" to turn the string into "let",
adds 100[d] + 101[e] + 101[e] to the cost.
Deleting "e" from "leet" adds 101[e] to the cost.
At the end, both strings are equal to "let", and the cost is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get costs of 433 or 417, which are higher.