848.Shifting Letters

848.Shifting Letters

难度:Medium

有一个由小写字母组成的字符串 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

确定每个字符移位的距离,实际上是数组逆向求和

class Solution {
public:
string shiftingLetters(string S, vector<int>& shifts) {
vector<int> nshifts(shifts.size(),0);
int sum=0;
for(int i=shifts.size()-1;i>=0;i--)
nshifts[i]=(sum =(sum +shifts[i])%26 );
string res;
for(int i=0;i<nshifts.size();i++)
{
int tmp=S[i]-'a';
tmp=(tmp+nshifts[i])%26;
res+= ('a'+ tmp);
}
return res;
}
};

执行用时 :72 ms, 在所有 C++ 提交中击败了46.53%的用户 内存消耗 :20.1 MB, 在所有 C++ 提交中击败了33.33%的用户