发表于 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 题目链接