【Leetcode 344】反转字符串

递归法

复杂度分析
时间复杂度：O(N)。执行了 N/2 次的交换。
空间复杂度：O(N)。递归过程中使用的堆栈空间。

java版本

static class Solution {
public void reverseString(char[] s) {
helper(s,0,s.length-1);
}

public void helper(char[] s,int left,int right){
if (left<right){
char temp=s[left];
s[left++]=s[right];
s[right--]=temp;
helper(s,left,right);
}
}
}

python版本

class Solution:
def reverseString(self, s):
def helper(left, right):
if left < right:
s[left], s[right] = s[right], s[left]
helper(left + 1, right - 1)
helper(0, len(s) - 1)

双指针法

java版本

class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char tmp = s[left];
s[left++] = s[right];
s[right--] = tmp;
}
// 可以用for循环进行同义替换
// for(int i=0;i<=s.length/2-1;i++){
// char temp = s[i];
// s[i]=s[s.length-1-i];
// s[s.length-1-i]=temp;
// }
}
}

python版本

class Solution:
def reverseString(self, s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left, right = left + 1, right - 1

复杂度分析

时间复杂度：O(N)。执行了 N/2 次的交换。
空间复杂度：O(1)，只使用了常数级空间

c++版本

class Solution {
public:
void reverseString(vector<char>& s) {
if (s.size()>0)
{
vector<char>::iterator p;
vector<char>::iterator q;
p = s.begin();
q = s.end()-1;
while (p < q)
{
char tmp = *p;
*p = *q;
*q = tmp;
p++;
q--;
}
}
}
};

vector::iterator 用法

参考链接：
​​​ https://leetcode-cn.com/problems/reverse-string/solution/shuang-zhi-zhen-by-1050669722/​​

​​https://leetcode-cn.com/problems/reverse-string/solution/fan-zhuan-zi-fu-chuan-by-leetcode/​​