Minimum total cost to convert one string into another using weighted character rules

You are given two strings, source and target, of the same length n, both made of lowercase English letters. You are also given a set of character conversion rules as three parallel lists original, changed and cost: rule j says that a single character equal to original[j] may be replaced by changed[j], and each such replacement costs cost[j].

You may apply rules any number of times, at any positions, in any order. Each application changes one character at one position and adds that rule's cost to the total. Return the minimum total cost needed to turn source into target, or -1 if it cannot be done.

Function Signature

def minimum_conversion_cost(source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:

Rules

• Rules are directed: a rule from a to b does not allow changing b into a.
• Rules may be chained at one position: with a rule from a to c and another from c to b, a position holding a can become b by applying both and paying both costs.
• Several rules may share the same original and changed pair with different costs; any of them may be used.
• A position where source and target already agree costs nothing.
• If even one position cannot be converted, the answer is -1.

Constraints

• 1 <= n <= 10^5 and len(source) == len(target) == n
• 1 <= len(original) == len(changed) == len(cost) <= 2000
• Every original[j] and changed[j] is a single lowercase English letter, and original[j] != changed[j]
• 1 <= cost[j] <= 10^6
• The answer can reach about 2.5 * 10^12, which exceeds 2^31 - 1; it always fits within 2^53, so return it as a plain integer.

Examples

Example 1

Input: source = "aab", target = "ccb", original = ["a", "b", "a"], changed = ["b", "c", "c"], cost = [1, 2, 5]
Output: 6

Changing a to c directly costs 5, but going from a to b and then from b to c costs 1 + 2 = 3. Positions 0 and 1 each cost 3, and position 2 already matches, so the total is 6.

Example 2

Input: source = "ab", target = "ba", original = ["a"], changed = ["b"], cost = [4]
Output: -1

Position 0 can become b for 4, but no rule or chain of rules turns b into a, so position 1 cannot be converted.

Example 3

Input: source = "ab", target = "bb", original = ["a", "a"], changed = ["b", "b"], cost = [7, 3]
Output: 3