Medium

题目描述

给定一个由小写英文字母组成的字符串 s 和一个长度相同的整数数组 shifts。

我们定义字母的移位操作为字母表中的下一个字母（循环进行，所以 ‘z’ 变成 ‘a’）。

例如，shift('a') = 'b'，shift('t') = 'u'，shift('z') = 'a'。

现在对于每个 shifts[i] = x，我们要将字符串 s 的前 i + 1 个字母移位 x 次。

返回所有移位操作完成后的最终字符串。

示例 1：

输入：s = "abc", shifts = [3,5,9]
输出："rpl"
解释：我们从 "abc" 开始。
将前 1 个字母移位 3 次后，得到 "dbc"。
将前 2 个字母移位 5 次后，得到 "igc"。
将前 3 个字母移位 9 次后，得到 "rpl"，这就是答案。

示例 2：

输入：s = "aaa", shifts = [1,2,3]
输出："gfd"

提示：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成
  • shifts.length == s.length
  • 0 <= shifts[i] <= 10^9

解题思路

这道题需要计算每个字符的总移位次数，然后应用到字符上。

关键观察： 对于位置 i 的字符，它会被所有 j >= i 的 shifts[j] 影响。换句话说，字符 s[i] 的总移位次数是 shifts[i] + shifts[i+1] + ... + shifts[n-1]。

解法分析：

  1. 直接计算法： 对每个位置计算所有影响它的移位次数之和，时间复杂度 O(n²)，会超时。

  2. 后缀和优化（推荐）： 从右向左计算后缀和，这样每个位置的总移位次数就是从该位置到末尾的移位次数之和。我们可以用一个变量累积这个和，避免额外的数组空间。

具体步骤：

  1. 从字符串末尾开始，维护一个累积的移位次数
  2. 对于每个位置，将当前的 shifts[i] 加到累积值上
  3. 计算字符移位：(原字符 - 'a' + 总移位次数) % 26，然后转回字符
  4. 注意要对移位次数取模 26，避免整数溢出

这种方法只需要一次遍历，时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    string shiftingLetters(string s, vector<int>& shifts) {
        long long totalShift = 0;
        int n = s.length();
        
        // 从右往左计算每个位置的总移位次数
        for (int i = n - 1; i >= 0; i--) {
            totalShift = (totalShift + shifts[i]) % 26;
            s[i] = ((s[i] - 'a' + totalShift) % 26) + 'a';
        }
        
        return s;
    }
};

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        total_shift = 0
        result = list(s)
        
        # 从右往左计算每个位置的总移位次数
        for i in range(len(s) - 1, -1, -1):
            total_shift = (total_shift + shifts[i]) % 26
            result[i] = chr((ord(s[i]) - ord('a') + total_shift) % 26 + ord('a'))
        
        return ''.join(result)

public class Solution {
    public string ShiftingLetters(string s, int[] shifts) {
        long totalShift = 0;
        char[] result = s.ToCharArray();
        
        // 从右往左计算每个位置的总移位次数
        for (int i = s.Length - 1; i >= 0; i--) {
            totalShift = (totalShift + shifts[i]) % 26;
            result[i] = (char)((result[i] - 'a' + totalShift) % 26 + 'a');
        }
        
        return new string(result);
    }
}

var shiftingLetters = function(s, shifts) {
    let totalShift = 0;
    let result = s.split('');
    
    // 从右往左计算每个位置的总移位次数
    for (let i = s.length - 1; i >= 0; i--) {
        totalShift = (totalShift + shifts[i]) % 26;
        let charCode = s.charCodeAt(i) - 97; // 'a' 的 ASCII 码是 97
        result[i] = String.fromCharCode((charCode + totalShift) % 26 + 97);
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1) 或 O(n)

说明：

  • 时间复杂度：只需要一次从右到左的遍历，每个字符处理一次
  • 空间复杂度：C++ 直接修改原字符串为 O(1)；Python/JavaScript 需要创建新的字符数组为 O(n)；C# 需要转换为字符数组为 O(n)

相关题目