原文链接: https://leetcode-cn.com/problems/shifting-letters

英文原文

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.

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

中文题目

有一个由小写字母组成的字符串 S，和一个整数数组 shifts。

我们将字母表中的下一个字母称为原字母的 移位（由于字母表是环绕的， 'z' 将会变成 'a'）。

例如·，shift('a') = 'b'， shift('t') = 'u',， 以及 shift('z') = 'a'。

对于每个 shifts[i] = x ， 我们会将 S 中的前 i+1 个字母移位 x 次。

返回将所有这些移位都应用到 S 后最终得到的字符串。

示例：

输入：S = "abc", shifts = [3,5,9]
输出："rpl"
解释： 
我们以 "abc" 开始。
将 S 中的第 1 个字母移位 3 次后，我们得到 "dbc"。
再将 S 中的前 2 个字母移位 5 次后，我们得到 "igc"。
最后将 S 中的这 3 个字母移位 9 次后，我们得到答案 "rpl"。

提示：

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

通过代码

官方题解

方法一：前缀和【通过】

思路

知道第 i 个字母最终移位多少次。

算法

因为对第 i 个字母及后面字母的移位都会导致第 i 个字母移位，所以第 i 个字母共移位 shifts[i] + shifts[i+1] + ... + shifts[shifts.length - 1] 次。

假设第 i 个字母移位 X 次，那么第 i + 1 个字母移位 X - shifts[i] 次。

例如 S.length = 4，那么 S[0] 移位 X = shifts[0] + shifts[1] + shifts[2] + shifts[3] 次，S[1] 移位 shifts[1] + shifts[2] + shifts[3] 次，S[2] 移位 shifts[2] + shifts[3] 次，以此类推。

当 i 增加时，令 X -= shifts[i] 计算下一个字母的移位次数。

[solution1-Java]
class Solution {
    public String shiftingLetters(String S, int[] shifts) {
        StringBuilder ans = new StringBuilder();
        int X = 0;
        for (int shift: shifts)
            X = (X + shift) % 26;

        for (int i = 0; i < S.length(); ++i) {
            int index = S.charAt(i) - 'a';
            ans.append((char) ((index + X) % 26 + 97));
            X = Math.floorMod(X - shifts[i], 26);
        }

        return ans.toString();
    }
}

[solution1-Python]
class Solution(object):
    def shiftingLetters(self, S, shifts):
        ans = []
        X = sum(shifts) % 26
        for i, c in enumerate(S):
            index = ord(c) - ord('a')
            ans.append(chr(ord('a') + (index + X) % 26))
            X = (X - shifts[i]) % 26

        return "".join(ans)

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是 S 和 shifts 的长度。

• 空间复杂度：$O(N)$，存储移位后的字符串。

统计信息

通过次数	提交次数	AC比率
9543	21319	44.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言