题目描述

[EN | CN]

给定一个字符串和一个整数 k,你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。如果剩余少于 k 个字符,则将剩余的所有全部反转。如果有小于 2k 但大于或等于 k 个字符,则反转前 k 个字符,并将剩余的字符保持原样。

示例:

1
2
输入: s = "abcdefg", k = 2
输出: "bacdfeg"

要求:

  1. 该字符串只包含小写的英文字母。
  2. 给定字符串的长度和 k 在 [1, 10000] 范围内。

解法 1:切割反转再拼接

直接按照题意,将原字符串切割成长度为 k 的子串,反转序数为奇数的子串,再拼接回去。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历与反转;
  • 空间复杂度为 $O(n)$,存储结果。

实现与结果如下:

1
2
3
4
5
6
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        substrs = [s[i:i + k] for i in range(0, len(s), k)]
        for i in range(0, len(substrs), 2):
            substrs[i] = substrs[i][::-1]
        return ''.join(substrs)
  • 执行用时:44 ms,在所有 Python3 提交中击败了 49.46% 的用户。

  • 内存消耗:13.9 MB,在所有 Python3 提交中击败了 28.57% 的用户。

解法 2:反转字符数组

其实不需要用「子串」,我们直接用字符数组来反转即可。

时间空间复杂度同上。

实现与结果如下:

1
2
3
4
5
6
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        chars = list(s)
        for i in range(0, len(chars), 2 * k):
            chars[i: i + k] = chars[i: i + k][::-1]
        return ''.join(chars)
  • 执行用时:36 ms,在所有 Python3 提交中击败了 81.54% 的用户。
  • 内存消耗:13.8 MB,在所有 Python3 提交中击败了 28.57% 的用户。

解法 3:递归

主要是定义一下当前状态的解、传递给下一状态、结束条件。可以简化到单行。

时间空间复杂度同上。

实现与结果如下:

1
2
3
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        return s[:k][::-1] + s[k:2*k] + self.reverseStr(s[2*k:], k) if s else ''
  • 执行用时:48 ms,在所有 Python3 提交中击败了 33.78% 的用户。
  • 内存消耗:13.9 MB,在所有 Python3 提交中击败了 28.57% 的用户。