768. Letter Conversion Cost
A print shop must turn the text source into the text target; both are lowercase and have the same length. A stamp machine has rules: rule i replaces the letter fromLetters[i] by the letter to[i] and costs cost[i] coins. Rules are one-way, may be applied to any position any number of times, and the same pair of letters can appear in several rules with different costs.
One step edits a single position, but a position may be passed through several intermediate letters before reaching the wanted one, and the cost is the sum of the rules used. Positions are independent. Return the minimum total cost to transform source into target, or -1 if some position cannot be made right. A position whose letters already match costs nothing.
Example 1
- Input:
- source = "pqr"target = "qrp"fromLetters = ["p","q","r","s","q"]to = ["q","r","s","p","p"]cost = [3,4,5,6,1]
- Output:
- 18
- Explanation:
p to q costs 3 and q to r costs 4; r to p has no direct rule, so r goes through s: 5 + 6 = 11. The total is 3 + 4 + 11 = 18.
Example 2
- Input:
- source = "aab"target = "aac"fromLetters = ["a","b"]to = ["b","a"]cost = [1,1]
- Output:
- -1
- Explanation:
No rule ever produces the letter c, so the last position cannot be fixed and the answer is -1.
Example 3
- Input:
- source = "kk"target = "mm"fromLetters = ["k","n","k"]to = ["n","m","m"]cost = [2,3,10]
- Output:
- 10
- Explanation:
Each k becomes m through n for 2 + 3 = 5, cheaper than the direct rule at 10, so two positions cost 10 in total.
Constraints
- 1 ≤ source.length = target.length ≤ 105
- 0 ≤ from.length = to.length = cost.length ≤ 105
- All letters are lowercase English letters (a-z) and from[i] ≠ to[i]
- 1 ≤ cost[i] ≤ 106
- The answer can exceed 32 bits; return a 64-bit integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(R + L + 26^3)
- Space
- O(26^2)