Change source into target by replacing individual characters. Rule i lets you change original[i] into changed[i] for a cost of cost[i]. You may apply rules repeatedly, including several changes at the same position. Rules are directed and may contain duplicate character pairs with different costs.
Return the minimum total cost to make the two strings equal. Return -1 if any required conversion is impossible. Characters already matching the target need no changes.
Example 1:
Input: source = "ab"
target = "cc"
original = ["a","a","b"]
changed = ["c","b","c"]
cost = [9,2,3]
Output: 8Explanation: Changing a directly to c costs 9, but the path a to b to c costs 2 + 3 = 5. Changing the second character b to c costs 3, giving a total of 8.
Example 2:
Input: source = "aaa"
target = "bbb"
original = ["a","a"]
changed = ["b","b"]
cost = [7,2]
Output: 6Explanation: Both rules change a to b. Use the cheaper rule, costing 2 per position, for a total cost of 6.
Example 3:
Input: source = "ac"
target = "bb"
original = ["a"]
changed = ["b"]
cost = [4]
Output: -1Explanation: The first character can become b for a cost of 4. There is no rule that changes c into b, so converting the entire string is impossible.
Constraints:
1 <= source.length == target.length <= 1000001 <= original.length == changed.length == cost.length <= 2000- The strings and rule characters contain only lowercase English letters.
original[i] != changed[i]1 <= cost[i] <= 1000000- Different rules may have the same original and changed characters.