541. Reverse String II

Problem

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and leave the other as original.

https://leetcode.cn/problems/reverse-string-ii/

Example 1:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Example 2:

Input: s = "abcd", k = 2
Output: "bacd"

Constraints:

• 1 <= s.length <= 10⁴
• s consists of only lowercase English letters.
• 1 <= k <= 10⁴

Test Cases

1
2

class Solution:
    def reverseStr(self, s: str, k: int) -> str:

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

import pytest

from solution import Solution


@pytest.mark.parametrize('s, k, expected', [
    ("abcdefg", 2, "bacdfeg"),
    ("abcd", 2, "bacd"),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, s, k, expected):
    assert sol.reverseStr(s, k) == expected

Thoughts

344. Reverse String 的进阶版，每 k 个字符为一段，对间隔的段做翻转。

先把 s 的所有字符放在数组里，然后分别对 s[0:k]、s[2k:3k]、s[4k:5k]、……按照 344. Reverse String 的逻辑进行翻转即可。

时间复杂度 O(n)，空间复杂度 O(n)。

Code

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

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        min2 = lambda a, b: a if a <= b else b
        n = len(s)
        arr = list(s)
        for i in range(0, len(arr), k << 1):
            l = i
            r = min2(i + k - 1, n - 1)
            while l < r:
                arr[l], arr[r] = arr[r], arr[l]
                l += 1
                r -= 1

        return ''.join(arr)

参考资料

• 本文引用

  • 344. Reverse String

许可协议

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

分享文章