A Price List for Letter Swaps

Medium

You are given two strings source and target of equal length made of lowercase English letters, plus a price list: for prices[i] any letter from_letters[i] can be replaced with the letter to_letters[i]. The same pair of letters may appear in the list several times with different prices. Replacements change one letter at a time, and a position can be changed as many times in a row as you like, for example a → c and then c → b. Return the minimum cost of turning source into target, or -1 if it cannot be done.

Example 1

source="cat", target="dog", from_letters=["c", "a", "t", "x"], to_letters=["d", "x", "g", "o"], prices=[3, 1, 4, 2] → 10

c → d for 3, a → x → o for 1 + 2 = 3, t → g for 4. Total 10.

Example 2

source="ab", target="ba", from_letters=["a"], to_letters=["b"], prices=[5] → -1

a can become b, but there is no way to turn b into a, so the answer is -1.

Example 3

source="zzz", target="zzz", from_letters=["z"], to_letters=["y"], prices=[7] → 0

Constraints

1 ≤ len(source) = len(target) ≤ 10⁵
source and target consist of lowercase English letters
1 ≤ len(prices) = len(from_letters) = len(to_letters) ≤ 2000
from_letters[i] and to_letters[i] are lowercase English letters, from_letters[i] ≠ to_letters[i]
1 ≤ prices[i] ≤ 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph Array String Shortest Path

Similar problems

Ratio Chain Queries Medium Ball Into the Hole Hard Phrase Rewrite Rules Hard Shortest Path of a Rolling Ball Medium Consistent Letter Equations Medium

Input

source="cat", target="dog", from_letters=["c", "a", "t", "x"], to_letters=["d", "x", "g", "o"], prices=[3, 1, 4, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 64 tests on the server, hidden ones included.