Cheapest Letter Dial

Medium

You are given two strings of equal length, source and target, and two arrays of 26 numbers each, forward_cost and backward_cost. The alphabet is arranged in a circle: 'a' comes again after 'z'. In one operation you pick any position i of source and either: - move its letter one step forward around the circle, which costs forward_cost[j], where j is the current letter's index in the alphabet ('a' is 0); - move its letter one step backward around the circle, which costs backward_cost[j] for the current letter with index j. Return the minimum total cost to turn source into target.

Example 1

source='cat', target='dog', forward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], backward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] → 26

Every step costs 1. 'c' → 'd' is one step forward; 'a' → 'o' takes 12 steps back, cheaper than 14 forward; 't' → 'g' is 13 steps either way. Total 1 + 12 + 13 = 26.

Example 2

source='b', target='a', forward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], backward_cost=[0, 100, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] → 25

One step back from 'b' costs 100, while going all the way round forward is 25 steps at 1 each. Forward wins: the answer is 25.

Example 3

source='abc', target='abc', forward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], backward_cost=[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] → 0

The strings already match, nothing needs turning, so the answer is 0.

Constraints

1 ≤ source.length == target.length ≤ 10⁵
source and target consist of lowercase English letters
forward_cost.length == backward_cost.length == 26
0 ≤ forward_cost[i], backward_cost[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array String Prefix Sum