2381. Shifting Letters II

Problem

You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [startᵢ, endᵢ, directionᵢ]. For every i, shift the characters in s from the index startᵢ to the index endᵢ (inclusive) forward if directionᵢ = 1, or shift the characters backward if directionᵢ = 0.

Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Similarly, shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that 'a' becomes 'z').

Return the final string after all such shifts to s are applied.

https://leetcode.com/problems/shifting-letters-ii/

Example 1:

Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
Output: "ace"
Explanation: Firstly, shift the characters from index 0 to index 1 backward. Now s = "zac".
Secondly, shift the characters from index 1 to index 2 forward. Now s = "zbd".
Finally, shift the characters from index 0 to index 2 forward. Now s = "ace".

Example 2:

Input: s = "dztz", shifts = [[0,0,0],[1,1,1]]
Output: "catz"
Explanation: Firstly, shift the characters from index 0 to index 0 backward. Now s = "cztz".
Finally, shift the characters from index 1 to index 1 forward. Now s = "catz".

Constraints:

• 1 <= s.length, shifts.length <= 5 * 10⁴
• shifts[i].length == 3
• 0 <= startᵢ <= endᵢ < s.length
• 0 <= directionᵢ <= 1
• s consists of lowercase English letters.

Test Cases

1
2

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:

1
2
3
4
5
6
7
8
9
10
11
12

import pytest

from solution import Solution


@pytest.mark.parametrize('s, shifts, expected', [
    ("abc", [[0,1,0],[1,2,1],[0,2,1]], "ace"),
    ("dztz", [[0,0,0],[1,1,1]], "catz"),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, s, shifts, expected):
    assert sol.shiftingLetters(s, shifts) == expected

Thoughts

848. Shifting Letters 的进阶版。

一个 [startᵢ, endᵢ, directionᵢ]，是对 s[startᵢ:endᵢ+1] 的每个字符往 directionᵢ 方向 shift，也可以看作是先对 s[startᵢ:] 每个字符按 directionᵢ 方向 shift 一次，再对 s[endᵢ+1:] 每个字符反方向 shift 一次。这样把 startᵢ 和 endᵢ 解耦，跟 848. Shifting Letters 就几乎一模一样了。

用数组记录每个位置，从其开始的每个字符要往哪个方向 shift 多少次（用正数表示 forward，负数表示 backward）。从 i = 0 开始遍历 s，同时累计需要 shift 的最终次数，对当前字符执行 shift，结果再拼成新的字符串即可。

时间复杂度 O(m + n)，空间复杂度 O(m + n)，其中 m、n 分别是 shifts 和 s 的长度。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

from string import ascii_lowercase


class Solution:
    def shiftingLetters(self, s: str, shifts: list[list[int]]) -> str:
        n = len(s)
        shifts2 = [0] * (n + 1)
        for start, end, d in shifts:
            if d == 0: d = -1
            shifts2[start] += d
            shifts2[end+1] -= d

        chars = ascii_lowercase
        mapping = {c: i for i, c in enumerate(chars)}

        parts = list(s)
        k = 0
        for i, c in enumerate(parts):
            k += shifts2[i]
            parts[i] = chars[(mapping[c] + k) % 26]

        return ''.join(parts)

参考资料

• 本文引用

  • 848. Shifting Letters

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章