欢迎来到李耶的频道【LeetCode面试题】。
反转字符串
题目
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组char[]的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]输入：s = ["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]解法一：双指针
思路：使用左右两个指针，分别指向数组的头和尾。交换两个指针指向的元素，然后左指针右移，右指针左移，直到两个指针相遇。这是最经典、最高效的原地反转解法。
functionreverseString(s){letleft=0;letright=s.length-1;while(left<right){[s[left],s[right]]=[s[right],s[left]];left++;right--;}returns;}- 时间复杂度 / 空间复杂度：O(n) / O(1)
- 优势：最推荐，代码简洁，性能最优，面试中最稳妥的写法
解法二：递归
思路：将数组的第一个和最后一个交换，然后递归处理中间的子数组。
functionreverseString(s){functionhelper(left,right){if(left>=right)return;[s[left],s[right]]=[s[right],s[left]];helper(left+1,right-1);}helper(0,s.length-1);returns;}- 时间复杂度 / 空间复杂度：O(n) / O(n)
- 优势：体现递归思想，但空间复杂度不满足 O(1) 要求，面试中不推荐
解法对比
| 解法 | 时间 / 空间复杂度 | 原地修改 | 推荐指数 |
|---|---|---|---|
| 双指针 | O(n) / O(1) | ✅ | ⭐⭐⭐⭐⭐ |
| 递归 | O(n) / O(n) | ✅ | ⭐⭐⭐ |
扩展题
- 反转字符串 II：给定一个字符串
s和一个整数k，从开头起每隔2k个字符，反转前k个字符。 - 反转字符串中的单词 III：给定一个字符串
s，反转每个单词的字符顺序，同时保留空格和单词顺序。 - 反转单词前缀：给定字符串
word和字符ch，找出ch第一次出现的下标i，反转从 0 到i的字符。
“世上无难事，只要肯登攀。” —— 毛泽东
关注李耶，每天一道面试题，一起卷起来 🔥
