848. Shifting Letters
Description
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'
, andshift('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.
Example 2:
Input: s = "aaa", shifts = [1,2,3] Output: "gfd"
Constraints:
1 <= s.length <= 105
s
consists of lowercase English letters.shifts.length == s.length
0 <= shifts[i] <= 109
Solutions
Solution 1: Suffix Sum
For each character in the string $s$, we need to calculate its final shift amount, which is the sum of $\textit{shifts}[i]$, $\textit{shifts}[i + 1]$, $\textit{shifts}[i + 2]$, and so on. We can use the concept of suffix sum, traversing $\textit{shifts}$ from back to front, calculating the final shift amount for each character, and then taking modulo $26$ to get the final character.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. Ignoring the space consumption of the answer, the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|