[Leetcode][344. Reverse String] 2 Approaches: Two Pointers and Recursion

By Long Luo

This article is the solution of Problem 344. Reverse String.

Here shows 2 Approaches to slove this problem, Recursion and Two Pointers.

Two Pointers

Most of us may think about two pointers solution.

We need N/2N/2 times swap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void reverseString(char[] s) {
if (s == null || s.length <= 1) {
return;
}

int left = 0;
int right = s.length - 1;
while (left < right) {
char ch = s[left];
s[left] = s[right];
s[right] = ch;
left++;
right--;
}
}

or use For Loop:

1
2
3
4
5
6
7
8
9
10
11
12
13
// Two Pointers Opt O(n) O(1)
public static void reverseString_tp_opt(char[] s) {
if (s == null || s.length <= 1) {
return;
}

int n = s.length;
for (int left = 0, right = n - 1; left < right; ++left, --right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(1)O(1)

Recursion

Recursive solution is also easy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void reverseString(char[] s) {
if (s == null || s.length <= 1) {
return;
}

reverse(s, 0, s.length - 1);
}

public void reverse(char[] str, int begin, int end) {
if (begin >= end) {
return;
}
char ch = str[begin];
str[begin] = str[end];
str[end] = ch;
reverse(str, begin + 1, end - 1);
}

Analysis

  • Time Complexity: O(n)O(n)
  • Space Complexity: O(n/2)O(n / 2)

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗