LeetCode 补充题 203. 反转字符串
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 344. 反转字符串
LeetCode 原题要求原地修改字符数组，额外空间为常数；本文接收 ASCII 字符串并返回新字符串，空串返回空串。
:::
给定 ASCII 字符串
s，返回字符顺序反转后的新字符串，空串返回空串。
示例 1：
输入：
s = "abcd"
输出："dcba"
提示：
- 本题按 ASCII 字符反转。
- 输入字符串不可原地修改。
题意分析
字符串不能原地修改，先复制到可写数组，再把位置 i 的字符与位置 n-1-i 的字符交换。题目限定 ASCII，因此 Go 按字节处理就与按字符处理一致。
解法：双指针交换
核心思路
[!blue]
左、右指针最初指向数组两端。每轮交换两端字符，使这两个位置都放上反转后的正确字符，再让左右指针各向中间移动一步。已经越过的位置无需再次处理。
当两指针相遇时，中间字符无需交换；交错时所有位置均已完成。因此循环条件使用 left < right。空串的右指针为 -1，会直接跳过循环，最后由数组构造新字符串。
解题步骤
- 将输入复制为可修改的字符或字节数组。
- 左指针从 0、右指针从最后一位开始，交换后同时向内移动。
- 两指针相遇或交错时停止，构造并返回新字符串。
代码实现
class Solution {
public String reverseString(String input) {
char[] s = input.toCharArray();
int left = 0;
int right = s.length - 1;
while (left < right) {
char value = s[left];
s[left] = s[right];
s[right] = value;
left++;
right--;
}
return new String(s);
}
}
func reverseString(input string) string {
s := []byte(input)
left := 0
right := len(s) - 1
for left < right {
s[left], s[right] = s[right], s[left]
left++
right--
}
return string(s)
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(n)$。
关键点总结
[!green]
将字符串复制到可变字符数组，双指针交换两端字符，再构造结果字符串。
易错点总结
[!yellow]
- 双指针移动本身只需常数空间，但输入副本和返回字符串仍占线性空间。
- 只在 left < right 时交换，不要反转到中点后又把字符换回去。
- Go 的字节反转依赖本题 ASCII 约束，不能直接推广到多字节字符。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 344. 反转字符串 | 简单 | 双指针交换两端字符的过程相同；该题原地修改字符数组且只用常数额外空间，本题返回新字符串，需要保存输出。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！