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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

By Long Luo

This article is the solution 2 Approaches: Two Pointers and Recursion 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 \(\dfrac {N}{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)\)
  • Space Complexity: \(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)\)
  • Space Complexity: \(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. 😉😃💗