541. 反转字符串 II
-
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
-
如果剩余字符少于 k 个，则将剩余字符全部反转。
-
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样
1.切片法: 通俗易懂, 代码简洁, 调试容易
class Solution(object):def reverseStr(self, s, k):""":type s: str:type k: int:rtype: str"""# 将字符串转换为列表方便操作s = list(s)# 遍历字符串(以2k为步长)for i in range(0, len(s), 2*k):# 如果剩余部分小于 k 个字符，反转所有剩余字符if len(s) - i < k:s[i:] = s[i:][::-1]# 如果剩余部分大于等于 k 且小于 2k，反转前 k 个字符elif len(s) - i >= k and len(s) - i < 2*k:s[i:i + k] = s[i:i + k][::-1]# 如果剩余部分大于等于 2k，反转前 k 个字符else:s[i:i + k] = s[i:i + k][::-1]# 将列表转换回字符串并返回return ''.join(s)
- 时间复杂度: O(n)
- 空间复杂度: O(n)
2.双指针: 更加节省空间, 但调试较难
class Solution(object):def reverseStr(self, s, k):""":type s: str:type k: int:rtype: str"""s = list(s)# 遍历每 2k 个字符for i in range(0, len(s), 2*k):# 反转前 k 个字符left, right = i, min(i + k - 1, len(s) - 1) # 右边界不能超过字符串长度while left < right:s[left], s[right] = s[right], s[left]left += 1right -= 1# 将列表转换回字符串并返回return ''.join(s)
- 时间复杂度: O(n)
- 空间复杂度: O(n)
