第144场双周赛题解：两个字符串得切换距离

两个字符串得切换距离

1、题目描述

给你两个长度相同的字符串 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 的 切换距离 。

2、解题思路

1、字符与字母表的映射：

• 字母表有 26 个字母，从 'a' 到 'z'。
• 每个字符都有对应的下标 index，计算公式为： $index=ord(c)-ord(a)$

2、切换规则：

• 从字符 s[i] 到 ，可能需要：
  1. 顺时针切换（下一个字母）。
  2. 逆时针切换（上一个字母）。
• 字符切换可能经过 0 到 25 个字母，因此需要考虑两种切换的代价并取较小值。

3、代价计算：

• 对于顺时针切换： $cost=nextcost[index(s[i])]+\dots +nextcost[index(t[i])]$
• 对于逆时针切换： $cost=previouscost[index(s[i])]+\dots +previouscost[index(t[i])]$

4、贪心策略：

• 对于每对字符 $(s[i],t[i])$，计算顺时针和逆时针切换的代价，选择较小值。

3、代码实现

class Solution {
public:
    long long shiftDistance(string s, string t, vector<int>& nextCost, vector<int>& previousCost) {
        int n = s.size();
        int alphabetSize = 26;   // 字母表大小
        long long totalCost = 0; // 使用 long long 防止溢出

        for (int i = 0; i < n; ++i) {
            int start = s[i] - 'a'; // 起始字符的下标
            int end = t[i] - 'a';   // 目标字符的下标

            // 计算顺时针代价
            long long clockwiseCost = 0;
            for (int j = start; j != end; j = (j + 1) % alphabetSize) {
                clockwiseCost += nextCost[j];
            }

            // 计算逆时针代价
            long long counterClockwiseCost = 0;
            for (int j = start; j != end; j = (j - 1 + alphabetSize) % alphabetSize) {
                counterClockwiseCost += previousCost[j];
            }

            // 累加到总代价中，选择顺时针和逆时针中的较小值
            totalCost += min(clockwiseCost, counterClockwiseCost);
        }

        return totalCost;
    }
};

关键点

1. 代价累加使用 long long：
   • totalCost、clockwiseCost 和 counterClockwiseCost 均使用 long long 类型，防止溢出。
2. 顺时针与逆时针的灵活计算：
   • 顺时针使用 (j + 1) % alphabetSize。
   • 逆时针使用 (j - 1 + alphabetSize) % alphabetSize。

4、复杂度分析

1. 时间复杂度：
   • 对于每个字符对 $(s[i],t[i])$，最多需要遍历 O(26) 次字母表。
   • 总时间复杂度为 $O(n\times 26)=O(n)$ 。
2. 空间复杂度：
   • 仅使用常数额外空间。
   • 空间复杂度为 O(1) 。