848-字母移位

LeetCode 848. Shifting Letters

LeetCode-848

You are given a string s of lowercase English letters and an integer array shifts of the same length.

Call the shift() of a letter, the next letter in the alphabet, (wrapping around so that ‘z’ becomes ‘a’).

For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'.
Now for each shifts[i] = x, we want to shift the first i + 1 letters of s, x times.

Return the final string after all such shifts to s are applied.

Example 1:

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.

method: 前缀和

从后往前进行前缀和，注意要模以26

字母移位逻辑：先减去'a'，映射到[0,25]，再加上要移动的位数，注意也要模以26

string shiftingLetters(string s, vector<int>& nums) {
    for (int i = nums.size() - 2; i >= 0; i--)
        nums[i] = (nums[i] + nums[i + 1]) % 26;
    nums.back() %= 26;  // 最后一个元素也要取模
    for (int i = 0; i < s.size(); i++) {
        s[i] = (s[i] - 'a' + nums[i]) % 26 + 'a';
    }
    return s;
}

可以合起来一起写，用一个数记录前缀和

string shiftingLetters(string s, vector<int>& nums) {
    int num = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        num = (num + nums[i]) % 26;
        s[i] = (s[i] - 'a' + num) % 26 + 'a';
    }
    return s;
}