Daily LeetCode 848. Shifting Letters

https://leetcode.com/problems/shifting-letters/

Medium

问题描述：

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

题目分析：

我们用题目中的例子来解释这条题目的含义：

给定字符串S="abc"，以及偏移数组shifts=[3, 5, 9]，我们需要对S进行偏移操作：

shifts[1] = 3，则将字符串中的前一个字符偏移三位，此时字符串变成"dbc"
shifts[2] = 5，则将字符串中的前两个字符偏移五位，此时字符串变成"igc"
shifts[3] = 9，则将字符串中的前三个字符偏移九位，此时字符串变成"rpl"
最终返回字符串"rpl"

这一题有两个要点：第一个要点是，我们可以将shift数组转换成对应的和数组，shift[i]表示对S[0:i]范围内的所有字符进行偏移操作，我们可以对shift数组执行反向累加和操作，那么第i项就是对应的第i个字符需要偏移的位数；第二个要点是，在得到了每个字符需要偏移的位数后，我们还需要考虑当前字符偏移到z后的后续处理，我们可以先算出当前字符到a的距离，加上偏移值后对26取余，得到偏移后的字符与a的距离，再加上a，就可以得到偏移后的字符。

还有一点需要注意，我最开始交的代码存在超时的问题，主要是因为我分别计算了反向累加和，多了几个循环，虽然都是O(n)的复杂度，但是在n的系数过大的情况下，就会导致超时。

代码：

class Solution(object):
    def shiftingLetters(self, S, shifts):
        """
        :type S: str
        :type shifts: List[int]
        :rtype: str
        """
        current_sum = sum(shifts)
        start = ord('a')
        res = ""

        for index in range(len(shifts)):
            res += chr((ord(S[index]) + current_sum - start) % 26 + start)
            current_sum -= shifts[index]

        return res