题目描述
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 <= S.length = shifts.length <= 200000 <= shifts[i] <= 10 ^ 9
解题思路
这道题比较简单，大概意思就是对于shifts数组中的每一个数，满足以下条件的字母都要向前移动这个数字的大小的步数：
- 这个数在数组中的下标大于或者等于字母在字符串中的下标
也就是说字符串中的第一个字母要移动，而第二个字母要移动
依次类推。如果一个字母移动之后大于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;
}
};
