0848-字母移位

有一个由小写字母组成的字符串 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 <= 105
• s 由小写英文字母组成
• shifts.length == s.length
• 0 <= shifts[i] <= 109

​​​​​​

方法一：前缀和【通过】

思路

知道第 i 个字母最终移位多少次。

算法

因为对第 i 个字母及后面字母的移位都会导致第 i 个字母移位，所以第 i 个字母共移位 shifts[i] + shifts[i+1] + ... + shifts[shifts.length - 1] 次。

假设第 i 个字母移位 X 次，那么第 i + 1 个字母移位 X - shifts[i] 次。

例如 S.length = 4，那么 S[0] 移位 X = shifts[0] + shifts[1] + shifts[2] + shifts[3] 次，S[1] 移位 shifts[1] + shifts[2] + shifts[3] 次，S[2] 移位 shifts[2] + shifts[3] 次，以此类推。

当 i 增加时，令 X -= shifts[i] 计算下一个字母的移位次数。

[solution1-Java]

class Solution {
    public String shiftingLetters(String S, int[] shifts) {
        StringBuilder ans = new StringBuilder();
        int X = 0;
        for (int shift: shifts)
            X = (X + shift) % 26;

        for (int i = 0; i < S.length(); ++i) {
            int index = S.charAt(i) - 'a';
            ans.append((char) ((index + X) % 26 + 97));
            X = Math.floorMod(X - shifts[i], 26);
        }

        return ans.toString();
    }
}

[solution1-Python]

class Solution(object):
    def shiftingLetters(self, S, shifts):
        ans = []
        X = sum(shifts) % 26
        for i, c in enumerate(S):
            index = ord(c) - ord('a')
            ans.append(chr(ord('a') + (index + X) % 26))
            X = (X - shifts[i]) % 26

        return "".join(ans)

复杂度分析

• 时间复杂度：O(N)，其中 N 是 S 和 shifts 的长度。

• 空间复杂度：O(N)，存储移位后的字符串。