题目描述

有一个由小写字母组成的字符串 S，和一个整数数组 shifts。

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

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

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

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

样例

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

注意

• 1 <= S.length = shifts.length <= 20000
• 0 <= shifts[i] <= 10 ^ 9

算法

(倒序枚举) $O(n)$

• 使用一个变量 tot 记录 shifts[i] 到末尾的总和，从数组末尾开始依次计算出这个字母需要移位的次数，然后通过模运算进行移位操作。

时间复杂度

• 只遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅定义了常数个变量，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    #define LL long long
    string shiftingLetters(string S, vector<int>& shifts) {
        int n = S.length();
        LL tot = 0;
        for (int i = n - 1; i >= 0; i--) {
            tot += shifts[i];
            S[i] = (S[i] - 'a' + tot) % 26 + 'a';
        }
        return S;
    }
};