Medium

题目描述

给定两个长度相同的字符串 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 的移位距离。

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length == t.length <= 10^5
  • s 和 t 仅由小写英文字母组成
  • nextCost.length == previousCost.length == 26
  • 0 <= nextCost[i], previousCost[i] <= 10^9

解题思路

这道题的核心是计算从字符 s[i] 转换到字符 t[i] 的最小成本。对于每一对字符，有两种转换路径：

  1. 顺时针路径：通过连续的 next 操作从源字符到目标字符
  2. 逆时针路径：通过连续的 previous 操作从源字符到目标字符

由于字母表是环形的，我们需要考虑两种情况的成本，然后选择较小的一个。

解题思路：

  1. 使用前缀和预计算所有可能的转换成本，避免重复计算
  2. 对于每个位置的字符转换，计算顺时针和逆时针的成本
  3. 选择成本较小的路径

具体实现：

  • 预计算 nextCost 和 previousCost 的前缀和，便于快速计算区间和
  • 对于从字符 a 到字符 b 的转换，计算两个方向的总成本
  • 顺时针：如果 a <= b，直接累加；否则需要绕一圈
  • 逆时针：如果 a >= b，直接累加；否则需要绕一圈
  • 取两者的最小值作为该位置的转换成本

时间复杂度为 O(n)，其中 n 是字符串长度，预计算部分为常数时间。

代码实现

class Solution {
public:
    long long shiftDistance(string s, string t, vector<int>& nextCost, vector<int>& previousCost) {
        vector<long long> nextPrefix(27, 0), prevPrefix(27, 0);
        
        // 预计算前缀和
        for (int i = 0; i < 26; i++) {
            nextPrefix[i + 1] = nextPrefix[i] + nextCost[i];
            prevPrefix[i + 1] = prevPrefix[i] + previousCost[i];
        }
        
        long long totalCost = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == t[i]) continue;
            
            int from = s[i] - 'a';
            int to = t[i] - 'a';
            
            // 计算顺时针成本
            long long clockwise;
            if (from <= to) {
                clockwise = nextPrefix[to] - nextPrefix[from];
            } else {
                clockwise = nextPrefix[26] - nextPrefix[from] + nextPrefix[to];
            }
            
            // 计算逆时针成本
            long long counterclockwise;
            if (from >= to) {
                counterclockwise = prevPrefix[from + 1] - prevPrefix[to + 1];
            } else {
                counterclockwise = prevPrefix[from + 1] + prevPrefix[26] - prevPrefix[to + 1];
            }
            
            totalCost += min(clockwise, counterclockwise);
        }
        
        return totalCost;
    }
};

class Solution:
    def shiftDistance(self, s: str, t: str, nextCost: List[int], previousCost: List[int]) -> int:
        # 预计算前缀和
        next_prefix = [0] * 27
        prev_prefix = [0] * 27
        
        for i in range(26):
            next_prefix[i + 1] = next_prefix[i] + nextCost[i]
            prev_prefix[i + 1] = prev_prefix[i] + previousCost[i]
        
        total_cost = 0
        
        for i in range(len(s)):
            if s[i] == t[i]:
                continue
                
            from_char = ord(s[i]) - ord('a')
            to_char = ord(t[i]) - ord('a')
            
            # 计算顺时针成本
            if from_char <= to_char:
                clockwise = next_prefix[to_char] - next_prefix[from_char]
            else:
                clockwise = next_prefix[26] - next_prefix[from_char] + next_prefix[to_char]
            
            # 计算逆时针成本
            if from_char >= to_char:
                counterclockwise = prev_prefix[from_char + 1] - prev_prefix[to_char + 1]
            else:
                counterclockwise = prev_prefix[from_char + 1] + prev_prefix[26] - prev_prefix[to_char + 1]
            
            total_cost += min(clockwise, counterclockwise)
        
        return total_cost

public class Solution {
    public long ShiftDistance(string s, string t, int[] nextCost, int[] previousCost) {
        long[] nextPrefix = new long[27];
        long[] prevPrefix = new long[27];
        
        // 预计算前缀和
        for (int i = 0; i < 26; i++) {
            nextPrefix[i + 1] = nextPrefix[i] + nextCost[i];
            prevPrefix[i + 1] = prevPrefix[i] + previousCost[i];
        }
        
        long totalCost = 0;
        
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == t[i]) continue;
            
            int from = s[i] - 'a';
            int to = t[i] - 'a';
            
            // 计算顺时针成本
            long clockwise;
            if (from <= to) {
                clockwise = nextPrefix[to] - nextPrefix[from];
            } else {
                clockwise = nextPrefix[26] - nextPrefix[from] + nextPrefix[to];
            }
            
            // 计算逆时针成本
            long counterclockwise;
            if (from >= to) {
                counterclockwise = prevPrefix[from + 1] - prevPrefix[to + 1];
            } else {
                counterclockwise = prevPrefix[from + 1] + prevPrefix[26] - prevPrefix[to + 1];
            }
            
            totalCost += Math.Min(clockwise, counterclockwise);
        }
        
        return totalCost;
    }
}

var shiftDistance = function(s, t, nextCost, previousCost) {
    const nextPrefix = new Array(27).fill(0);
    const prevPrefix = new Array(27).fill(0);
    
    // 预计算前缀和
    for (let i = 0; i < 26; i++) {
        nextPrefix[i + 1] = nextPrefix[i] + nextCost[i];
        prevPrefix[i + 1] = prevPrefix[i] + previousCost[i];
    }
    
    let totalCost = 0;
    
    for (let i = 0; i < s.length; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是字符串长度。预计算前缀和需要 O(26) = O(1) 时间，遍历字符串需要 O(n) 时间
空间复杂度O(1)，只使用了两个长度为 27 的数组存储前缀和，空间使用是常数级别的

相关题目