leetcode_双指针 541. 反转字符串 II

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 += 1
                right -= 1
        
        # 将列表转换回字符串并返回
        return ''.join(s)

• 时间复杂度: O(n)
• 空间复杂度: O(n)