题目描述

给你两个长度相同的字符串 s 和 t，以及两个整数数组 nextCost 和 previousCost。

一次操作中，你可以选择 s 中的一个下标 i，执行以下操作 之一 ：

• 将 s[i] 切换为字母表中的下一个字母，如果 s[i] == 'z'，切换后得到 'a'。操作的代价为 nextCost[j]，其中 j 表示 s[i] 在字母表中的下标。
• 将 s[i] 切换为字母表中的上一个字母，如果 s[i] == 'a'，切换后得到 'z'。操作的代价为 previousCost[j]，其中 j 是 s[i] 在字母表中的下标。

切换距离 指的是将字符串 s 变为字符串 t 的 最少 操作代价总和。

请你返回从 s 到 t 的 切换距离。

样例

输入：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]

输出：2

解释：

选择下标 i = 0 并将 s[0] 向前切换 25 次，总代价为 1。
选择下标 i = 1 并将 s[1] 向后切换 25 次，总代价为 0。
选择下标 i = 2 并将 s[2] 向前切换 25 次，总代价为 1。
选择下标 i = 3 并将 s[3] 向后切换 25 次，总代价为 0。

输入：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]

输出：31

解释：

选择下标 i = 0 并将 s[0] 向前切换 9 次，总代价为 9。
选择下标 i = 1 并将 s[1] 向后切换 10 次，总代价为 10。
选择下标 i = 2 并将 s[2] 向前切换 1 次，总代价为 1。
选择下标 i = 3 并将 s[3] 向后切换 11 次，总代价为 11。

限制

• 1 <= s.length == t.length <= 10^5
• s 和 t 都只包含小写英文字母。
• nextCost.length == previousCost.length == 26
• 0 <= nextCost[i], previousCost[i] <= 10^9

算法

(前缀和) $O(n + |\Sigma|)$

1. 两个字符切换的代价共有两种计算方式，一种是不断向后切换，另一种是不断向前切换。
2. 分别求出向后切换以及向前切换的前缀和，方便快速计算两种切换方式的代价。
3. 遍历字符串，如果字符不一样，则按照上面的方式求最小切换代价。

时间复杂度

• 预处理的时间复杂度为 $O(|\Sigma|)$。
• 遍历字符串计算答案的时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(n + |\Sigma|)$。

空间复杂度

• 需要 $O(|\Sigma|)$ 的额外空间存储前缀和数组。

C++ 代码

#define LL long long

class Solution {
public:
    LL shiftDistance(string s, string t, vector<int>& nextCost, vector<int>& previousCost) {
        vector<LL> sum_next(26, 0), sum_prev(26, 0);

        sum_next[0] = nextCost[0];
        sum_prev[0] = previousCost[0];
        for (int i = 1; i < 26; i++) {
            sum_next[i] = sum_next[i - 1] + nextCost[i];
            sum_prev[i] = sum_prev[i - 1] + previousCost[i];
        }

        const int n = s.size();
        LL ans = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == t[i])
                continue;

            int x = s[i] - 'a', y = t[i] - 'a';
            ans += min(
                x < y ? 
                    (sum_next[y - 1] - (x > 0 ? sum_next[x - 1] : 0)) :
                    (
                        sum_next[25] -
                            (sum_next[x - 1] - (y > 0 ? sum_next[y - 1] : 0))
                    ),
                x > y ?
                    (sum_prev[x] - sum_prev[y]) :
                    (sum_prev[25] - (sum_prev[y] - sum_prev[x]))
            );
        }

        return ans;
    }
};