Shift Distance Between Two Strings
You are given two strings s and t of the same length, and two integer arrays nextCost and previousCost.
In one operation, you can pick any index i of s, and perform either one of the following actions:
- Shift
s[i]to the next letter in the alphabet. Ifs[i] == 'z', replace it with'a'. This operation costsnextCost[j], wherejis the index ofs[i]in the alphabet. - Shift
s[i]to the previous letter in the alphabet. Ifs[i] == 'a', replace it with'z'. This operation costspreviousCost[j], wherejis the index ofs[i]in the alphabet.
The shift distance is the minimum total cost of operations required to transform s into t.
Return the shift distance from s to t.
Example 1
Input
s = "abab", t = "baba", nextCost = [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,0], previousCost = [1,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]Output
2Shifting characters at indices 0 and 2 backward costs 1 each, while shifting indices 1 and 3 forward costs 0, for a total cost of 2.
Example 2
Input
s = "leet", t = "code", nextCost = [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], previousCost = [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]Output
31The cheapest shifts for the four positions cost 9, 10, 1, and 11 respectively, for a total cost of 31.
Constraints
- 1 <= s.length == t.length <= 10^5
- s and t consist only of lowercase English letters.
- nextCost.length == previousCost.length == 26
- 0 <= nextCost[i], previousCost[i] <= 10^9