0344. Reverse String

题目信息

题号:

0344

难度:

Easy

主题:

字符数组、原地修改、顺序反转、常数空间

原题:

LeetCode 0344

重点:

输入是可修改字符数组、函数无返回值、每个字符移动到镜像位置、额外空间必须为 O(1)

题目重述

给定字符数组 s,在原数组上把字符顺序完全反转。反转后,原下标 i 的字符应位于下标 s.length-1-i;字符本身不能改变、丢失或重复。

函数通过修改 s 返回结果,不应构造并返回另一个字符串或同长度数组。s 的长度位于 [1, 10^5],每个元素是可打印 ASCII 字符。题目要求只使用 O(1) 额外空间。

自建示例

包含大小写和标点:

输入:s = ["C", "o", "d", "e", "!"]
修改后:["!", "e", "d", "o", "C"]
解释:字符按下标顺序整体反转,感叹号从末尾移动到开头。

单字符数组:

输入:s = ["?"]
修改后:["?"]
解释:唯一字符的镜像位置仍是自身。

从两端向中间交换

下标 left 与 right = n - 1 - left 互为镜像。只要 left < right,交换这两个位置并让两个指针向中间移动,就能一次确定一对字符的最终位置;指针相遇或交错时,所有位置都已经处理。

C++ 实现

class Solution {
public:
    void reverseString(std::vector<char>& s) {
        int left = 0;
        int right = static_cast<int>(s.size()) - 1;
        while (left < right) {
            std::swap(s[left++], s[right--]);
        }
    }
};

代码分析

每次交换把一对镜像位置放到正确字符,未处理区间严格缩小;单字符或空边界不会进入循环。算法原地完成,时间复杂度为 O(n),额外空间为 O(1)。