字母移位 II

标签: 数组 字符串 前缀和

难度: Medium

给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，其中 shifts[i] = [starti, endi, directioni] 。对于每个 i ，将 s 中从下标 starti 到下标 endi （两者都包含）所有字符都进行移位运算，如果 directioni = 1 将字符向后移位，如果 directioni = 0 将字符向前移位。

将一个字符 向后 移位的意思是将这个字符用字母表中 下一个 字母替换（字母表视为环绕的，所以 'z' 变成 'a'）。类似的，将一个字符 向前 移位的意思是将这个字符用字母表中 前一个 字母替换（字母表是环绕的，所以 'a' 变成 'z' ）。

请你返回对 s 进行所有移位操作以后得到的最终字符串。

示例 1：

输入：s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
输出："ace"
解释：首先，将下标从 0 到 1 的字母向前移位，得到 s = "zac" 。
然后，将下标从 1 到 2 的字母向后移位，得到 s = "zbd" 。
最后，将下标从 0 到 2 的字符向后移位，得到 s = "ace" 。

示例 2:

输入：s = "dztz", shifts = [[0,0,0],[1,1,1]]
输出："catz"
解释：首先，将下标从 0 到 0 的字母向前移位，得到 s = "cztz" 。
最后，将下标从 1 到 1 的字符向后移位，得到 s = "catz" 。

提示：

  • 1 <= s.length, shifts.length <= 5 * 104
  • shifts[i].length == 3
  • 0 <= starti <= endi < s.length
  • 0 <= directioni <= 1
  • s 只包含小写英文字母。

Submission

运行时间: 104 ms

内存: 38.9 MB

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        # 差分
        n = len(s)
        lst = [0] * (n + 1)
        for start, end, direct in shifts:
            lst[start] += (-1, 1)[direct]
            lst[end + 1] -= (-1, 1)[direct]
        cur = 0
        for i, ch in enumerate(s):
            cur += lst[i]
            lst[i] = chr((ord(ch) - 97 + cur) % 26 + 97)
        lst.pop()
        return "".join(lst)

Explain

该题解使用了差分数组的方法来优化连续区间的更新。对于每个shift操作，而不是直接更新字符串s的每个字符，我们在辅助数组lst中标记起始点和终点的变化。如果directioni是1（向后移位），在起始位置增加1，在终点的下一个位置减少1；如果是0（向前移位），则在起始位置减少1，在终点的下一个位置增加1。这样，我们只需要在lst上做两次操作即可标记一个区间的移位。之后，我们通过累加lst来计算实际的移位次数，并应用到字符串s上，计算最终的字符位置。

时间复杂度: O(m + n)

空间复杂度: O(n)

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        # 初始化长度为n+1的差分数组，用于记录每个位置的累积移位
        n = len(s)
        lst = [0] * (n + 1)
        for start, end, direct in shifts:
            lst[start] += (-1, 1)[direct]  # 根据direction修改起始位置值
            lst[end + 1] -= (-1, 1)[direct]  # 修改终点后一个位置的值，形成区间
        cur = 0
        # 应用差分数组中的移位到字符串s
        for i, ch in enumerate(s):
            cur += lst[i]  # 累计到当前位置的移位总和
            lst[i] = chr((ord(ch) - 97 + cur) % 26 + 97)  # 计算移位后的字符并转为字符
        lst.pop()  # 移除多余的最后一个元素
        return ''.join(lst)  # 字符数组转换为字符串

Explore

在差分数组中，初始化长度为n+1的目的是为了方便处理区间的结束位置。当我们对一个区间[start, end]进行操作时，为了使end位置之后的元素不受影响，我们在end+1位置进行一个相反的操作。如果数组只有长度n，那么当end等于n-1（即区间结束于数组末尾）时，end+1将是n，这将越界如果数组长度只是n。因此，为了安全地应用这种操作而不越界，数组长度设置为n+1。

表达式(-1, 1)[direct]是Python中的一个条件表达式，它根据direct的值选择-1或1。这里，direct是一个指示移动方向的标志，通常0代表向前移动（向左或逆时针），1代表向后移动（向右或顺时针）。如果direct为0，(-1, 1)[0]将结果为-1，表示字符需要向前移动；如果direct为1，(-1, 1)[1]将结果为1，表示字符需要向后移动。这是一个简洁的方法来根据方向设置增加或减少的值。

在差分数组中，终点后一个位置的相反操作是为了限定移位操作只影响区间[start, end]内的元素。通过在start位置增加一个值，并在end+1位置减去相同的值，我们创建了一个区间内的‘区间增量’。这样，当我们累加数组以应用这些变化时，只有在start到end的位置会受到影响，end之后的位置则不会累积这个特定的变化，从而保持了区间之外的数据稳定。

这个表达式是基于ASCII码计算字符移位的通用方法。首先，ord(ch) - 97将字符ch（假设是小写字母）转换为0-25之间的整数，其中'a'变为0，'z'变为25。然后加上cur表示移位的数量，可以是正数或负数。使用模26操作确保结果再次落在0-25的范围内，这对应于字母表中的循环移位。最后，再加上97将数字转换回对应的ASCII字符。这种方法有效地处理了字母表循环和任意方向的移位。