字母移位

难度: Medium

有一个由小写字母组成的字符串 s，和一个长度相同的整数数组 shifts。

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

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

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

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

示例 1：

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

示例 2:

输入: s = "aaa", shifts = [1,2,3]
输出: "gfd"

提示:

1 <= s.length <= 10⁵
s 由小写英文字母组成
shifts.length == s.length
0 <= shifts[i] <= 10⁹

Submission

运行时间: 100 ms

内存: 26.7 MB

class Solution(object):
    def shiftingLetters(self, s: str, shifts: List[int]):
        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)

Explain

此题解使用了一种巧妙的方法来避免重复计算多次移位，从而实现高效的字符串转换。首先，计算所有移位的总和，并对26取模，因为字母表循环的周期为26。然后遍历字符串中的每个字符，对于每个字符，计算其应当移位后的新位置，使用ASCII码转换来实现。在每次遍历中，通过减去当前位置的移位数并再次对26取模，动态地更新移位总和，这样可以保证每个字符都移位正确的次数。这种方法有效利用了前缀和思想，减少了重复的计算。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution(object):
    def shiftingLetters(self, s: str, shifts: List[int]):
        ans=[]  # 用于收集结果字符
        X = sum(shifts) % 26  # 计算所有移位总和，并对26取模以处理循环
        for i, c in enumerate(s):  # 遍历字符串中的每个字符
            index = ord(c) - ord('a')  # 计算字符c的字母表索引
            ans.append(chr(ord('a') + (index + X) % 26))  # 计算并存储新字符
            X = (X - shifts[i]) % 26  # 更新X，减去当前字符的移位数，保证后续字符正确移位

        return ''.join(ans)  # 将结果字符列表转换为字符串

Explore

在字母表中，只有26个字母，因此任何关于字母位置的计算都需要对26取模来确保结果不会超出字母表范围。这样做可以实现循环移位，例如，超出'z'的移位可以从'a'开始重新计算。对26取模是为了处理这种周期性，并且使计算更高效，避免处理不必要的大数。

计算`(index + X) % 26`确保了无论X是多少，结果始终在0到25之间，这对应于字母表中的位置。这种计算考虑了所有可能的移位，并将其规范化到一个完整的字母表周期内。这意味着无论原始位置和移位的大小，最终结果总是一个有效的字母位置。

是的，这种方法考虑了负数取模的情况。在Python中，当使用负数进行取模运算时，结果保持为非负数，这对于保持移位总和`X`在正确的范围内是必要的。这确保了每次减去一个字符的移位值后，剩余的移位总和仍然是有效的，可以正确应用于后续的字符。

即使`shifts`数组中的元素非常大，对这些值取26的模仍然是有效的。这是因为字母表的周期是26，所以任何大于26的移位数在实际效果上等同于它除以26的余数。例如，移位100次和移位100 % 26次产生的效果相同。这样，无论移位值的大小如何，取模操作都保证了计算的正确性和效率。