3361. 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. If s[i] == 'z', you should replace it with 'a'. This operation costs nextCost[j] where j is the index of s[i] in the alphabet.
• Shift s[i] to the previous letter in the alphabet. If s[i] == 'a', you should replace it with 'z'. This operation costs previousCost[j] where j is the index of s[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.

class Solution {
public:
    long long shiftDistance(string initialWord, string finalWord, vector<int>& nextCost, vector<int>& previousCost) {
        vector<vector<long long>> cost(26, vector<long long>(26, 1ll<<48));
        for(int i = 0; i < 26; i++) {
            cost[i][(i+1)%26] = nextCost[i];
            cost[i][(i+25)%26] = previousCost[i];
            cost[i][i] = 0;
        }
        for(int k = 0; k < 26; k++) {
            for(int i = 0; i < 26; i++) {
                for(int j = 0; j < 26; j++) {
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
                }
            }
        }
        long long res = 0;
        for(int i = 0; i < initialWord.size(); i++) {
            res += cost[initialWord[i]-'a'][finalWord[i]-'a'];
        }
        return res;
    }
};