反转字符串 II

标签: 双指针 字符串

难度: Easy

给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个,则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。

示例 1:

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

示例 2:

输入:s = "abcd", k = 2
输出:"bacd"

提示:

  • 1 <= s.length <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104

Submission

运行时间: 19 ms

内存: 16.0 MB

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        result = ''
        for i in range(0, len(s), 2 * k):
            segment = s[i:i + k]
            result += segment[::-1] + s[i + k:i + 2 * k]
        return result

Explain

该题解采用遍历字符串的方式,每次步进2k个字符,处理每个分段。对每个分段的前k个字符进行反转,并将反转后的字符串与该分段的后k个字符(如果存在)相连,累加到结果字符串中。这样可以确保每次处理都符合题目的要求,即每2k个字符中的前k个字符被反转,后k个字符保持不变。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        result = ''
        for i in range(0, len(s), 2 * k):  # 从0开始,每次增加2k步进处理字符串
            segment = s[i:i + k]  # 取前k个字符
            result += segment[::-1] + s[i + k:i + 2 * k]  # 反转前k个字符并拼接后k个字符
        return result  # 返回最终处理后的字符串

Explore

在Python中,字符串切片操作s[i:j]会在索引i到j-1的范围内提取字符。如果j超出了字符串的实际长度,切片操作会自动停止在字符串的末尾,不会引起错误。因此,通过在每次循环中尝试取i到i+k和i+k到i+2k的切片,代码自动适应了字符串长度不是2k倍数的情况。对于最后一个分段,如果长度小于k,会反转整个分段;如果长度在k和2k之间,只有前k个字符被反转,剩余的字符保持原样。

当k值非常小(如1)时,每次反转仅涉及一个字符,这在性能上不是问题。但当k值非常大时,反转操作可能涉及大量字符,这可能导致显著的性能下降,尤其是在字符串本身长度也很大的情况下。为了优化,可以考虑使用更高效的数据结构,如列表(数组),因为列表的元素更新比字符串(不可变)更高效。将字符串转换为列表,进行反转操作后,再将列表转换回字符串可以提高性能。

Python中的字符串是不可变的,这意味着每次修改字符串实际上都会创建一个新的字符串对象。这在反复操作大型字符串时可能导致性能问题。在题解中,通过构建一个新的字符串并累加结果来避免反复修改原始字符串。此外,可以进一步优化性能,通过使用列表来存储各个部分的字符串,最后使用join方法将它们合并成一个字符串,这样可以减少创建不必要的中间字符串。

代码中没有特别处理`i + k`和`i + 2 * k`范围超出字符串长度的情况,因为Python的切片操作自然地处理了这种情况。如果切片的结束索引超出了字符串的长度,Python将只返回从开始索引到字符串末尾的子字符串。这种行为确保了即使在字符串的末尾也不会产生错误或需要额外的逻辑来处理边界条件。