【LeetCode】反转字符串

欢迎来到李耶的频道【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) 要求，面试中不推荐

解法对比

扩展题

1. 反转字符串 II：给定一个字符串s和一个整数k，从开头起每隔2k个字符，反转前k个字符。
2. 反转字符串中的单词 III：给定一个字符串s，反转每个单词的字符顺序，同时保留空格和单词顺序。
3. 反转单词前缀：给定字符串word和字符ch，找出ch第一次出现的下标i，反转从 0 到i的字符。

“世上无难事，只要肯登攀。” —— 毛泽东

关注李耶，每天一道面试题，一起卷起来 🔥