848. Shifting Letters（week13）

题目描述

We have a string S of lowercase letters, and an integer array shifts.

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.

Note:

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

解题思路

这道题比较简单，大概意思就是对于shifts数组中的每一个数，满足以下条件的字母都要向前移动这个数字的大小的步数：

1. 这个数在数组中的下标大于或者等于字母在字符串中的下标

也就是说字符串中的第一个字母要移动，而第二个字母要移动 依次类推。如果一个字母移动之后大于z，则取从a开始继续算大于的步数。

时间复杂度

O(n)

空间复杂度

开辟一个数组，复杂度为O(n)

源码

class Solution {
public:
  string shiftingLetters(string S, vector<int>& shifts) {
    vector<int> sumOfShifts;
    long long _sum = 0;
    for (int i = shifts.size() - 1; i >= 0; --i) {
      _sum += shifts[i] % 26;
      sumOfShifts.push_back(_sum);
    }
    for (int i = 0, j = shifts.size() - 1; i < shifts.size(); ++i, --j) {
      long long current = sumOfShifts[j];
      int numOfChar = S[i] - 'a';
      numOfChar += current;
      numOfChar %= 26;
      S[i] = 'a' + numOfChar;
    }
    return S;
  }
};