0344.反转字符串

难度：🟢 简单

标签：双指针、字符串、递归

链接：344. 反转字符串

题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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"]

解题思路

核心思想

本题的核心是在不使用额外数组的情况下，原地反转一个字符数组。最直接的方法就是交换数组的第一个和最后一个元素，第二个和倒数第二个元素，以此类推，直到数组的中心。

思路选择

双指针法 是解决此问题的标准最优思路。

• 我们定义两个指针，left 指向数组的头部，right 指向数组的尾部。

• 在一个循环中，我们交换 left 和 right 指针指向的字符。

• 交换完成后，left 指针向右移动，right 指针向左移动，不断向数组中心靠拢，直到两个指针相遇或交错。

关键步骤

1. 初始化指针：left = 0，right = s.length - 1。

2. 循环条件：当 left < right 时，表示还有未交换的对称元素，持续循环。

3. 交换元素：交换 s[left] 和 s[right] 的值。

4. 移动指针：left 指针加一，right 指针减一。

5. 完成：循环结束后，数组 s 就被成功地原地反转了。

代码实现

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
    let left = 0, right = s.length - 1;

    while (left < right) {
        // 使用解构赋值交换元素
        [s[left], s[right]] = [s[right], s[left]];

        // 移动指针
        left++;
        right--;
    }
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是字符数组 s 的长度。我们需要遍历大约一半的数组元素来进行交换。

• 空间复杂度：O(1) 我们只使用了 left 和 right 两个额外变量作为指针，是在原地进行修改，空间消耗是恒定的。

相关题目

• 0092.反转链表 II

• 0206.反转链表

• 0541.反转字符串 II

总结

本题是双指针算法的入门级经典应用。通过头尾两个指针相向移动并交换元素，可以非常直观且高效地解决原地反转问题。这个模型在数组和字符串处理中非常常见。