反转字符串

标签: 双指针 字符串

难度: Easy

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符

Submission

运行时间: 18 ms

内存: 21.1 MB

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        for i in range(len(s)//2):
            s[i],s[-i-1] = s[-i-1],s[i]

Explain

这个题解采用了双指针的思路。定义两个指针分别指向字符串的起点和终点，然后不断交换两个指针指向的字符，同时将两个指针向中间移动，直到两个指针相遇。这样就实现了反转字符串的目的。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        # 使用双指针 i 和 -i-1，分别指向字符串的起点和终点
        for i in range(len(s)//2):
            # 交换两个指针指向的字符
            s[i], s[-i-1] = s[-i-1], s[i]
            # 指针向中间移动

Explore

双指针方法用于字符串反转问题因为它能够高效地在原地（不使用额外空间）完成操作，是时间复杂度为O(n)和空间复杂度为O(1)的解决方案。此外，存在其他方法如使用栈，每次迭代将字符放入栈中，然后再将其弹出到一个新的字符串中，但这需要额外的空间；还可以简单地使用字符串或列表的内置函数（例如Python中的`reversed`或切片`s[::-1]`），但这些通常不满足原地修改的要求。

在Python中，负索引用于从列表的末尾开始访问元素。索引`-i-1`的计算方式是，`-1`是列表中最后一个元素的索引，`-i-1`则表示从最后一个元素开始向左移动`i`个位置。例如，在列表`['a', 'b', 'c', 'd']`中，索引`-1`对应元素`'d'`，`-2`对应`'c'`，依此类推。这种索引方式简化了对列表尾部的访问，使代码更简洁易读。

在双指针方法中，通过精确计算循环条件`i < len(s)//2`确保不会出现越界错误。这个条件确保了指针`i`始终指向数组的前半部分，而`-i-1`始终有效地指向对应的后半部分元素。因此，在索引有效的范围内操作，避免了越界的风险。

这种原地反转的方法适用于所有类型的字符数组，包括包含特殊字符或Unicode字符的数组。在Python中，字符串实际上是Unicode字符序列，而列表则可以容纳任意类型的对象。因此，无论字符数组包含的是ASCII字符、扩展的Latin字符、汉字、表情符号等Unicode字符，双指针方法都能有效工作，并且不影响字符的内部表示。