JZX轻语：简

LeetCode 848 - 字母移位

发表于2024年05月14日

#前缀和

对于这种带有累加意味的题目，可以考虑前缀和思想，不过该题其实是后缀和，从右往左累加移位次数，然后再遍历一次字符串，一次完成移位操作即可。需要注意的是移位次数可能会比较大，需要取模；且小写字母的移位操作为chr(ord_a + ((ord(s[i]) - ord_a) + suffix_sum[i]) % 26).

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        # 反向前缀和?
        ord_a = ord('a')  # 预计算a的ascii
        suffix_sum = [0] * len(shifts)
        acc_sum = 0
        for i in range(len(shifts) - 1, -1, -1):
            acc_sum = (acc_sum + shifts[i]) % 26  # 在这里mod 26
            suffix_sum[i] = acc_sum
        ans = []
        for i in range(len(s)):
            # 注意这里的小写字母移位
            new_ord = ord_a + ((ord(s[i]) - ord_a) + suffix_sum[i]) % 26
            ans.append(chr(new_ord))
        return ''.join(ans)

闪念标签：LC

题目链接：https://leetcode.cn/problems/shifting-letters/