0848. 字母移位【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 后缀和

1. 📝 题目描述

• leetcode

有一个由小写字母组成的字符串 s，和一个长度相同的整数数组 shifts。

我们将字母表中的下一个字母称为原字母的 移位 shift() （由于字母表是环绕的， 'z' 将会变成 'a'）。

• 例如，shift('a') = 'b', shift('t') = 'u', 以及 shift('z') = 'a'。

对于每个 shifts[i] = x， 我们会将 s 中的前 i + 1 个字母移位 x 次。

返回 将所有这些移位都应用到 s 后最终得到的字符串。

---

示例 1：

输入：s = "abc", shifts = [3,5,9]
输出："rpl"
解释：
我们以 "abc" 开始。
将 S 中的第 1 个字母移位 3 次后，我们得到 "dbc"。
再将 S 中的前 2 个字母移位 5 次后，我们得到 "igc"。
最后将 S 中的这 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

​​​​​​

2. 🎯 s.1 - 后缀和

c

char* shiftingLetters(char* s, int* shifts, int shiftsSize) {
    int n = strlen(s);
    char* res = (char*)malloc(n + 1);
    strcpy(res, s);
    long long total = 0;
    for (int i = n - 1; i >= 0; i--) {
        total = (total + shifts[i]) % 26;
        res[i] = (s[i] - 'a' + total) % 26 + 'a';
    }
    res[n] = '\0';
    return res;
}

js

/**
 * @param {string} s
 * @param {number[]} shifts
 * @return {string}
 */
var shiftingLetters = function (s, shifts) {
  const n = s.length
  let total = 0
  const res = [...s]
  for (let i = n - 1; i >= 0; i--) {
    total = (total + shifts[i]) % 26
    res[i] = String.fromCharCode(((s.charCodeAt(i) - 97 + total) % 26) + 97)
  }
  return res.join('')
}

py

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        n = len(s)
        total = 0
        res = list(s)
        for i in range(n - 1, -1, -1):
            total = (total + shifts[i]) % 26
            res[i] = chr((ord(s[i]) - 97 + total) % 26 + 97)
        return ''.join(res)

• 时间复杂度：$O(n)$，其中 n 是字符串长度
• 空间复杂度：$O(n)$

算法思路：

• 从右向左累加移位量，每个位置的总移位 = 后缀和
• 对每个字符应用总移位量并取模 26