Solutions

1. Array

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        tmp = []
        for i in range(len(s) - 1, -1, -1):
            tmp.append(s[i])
        for i in range(len(s)):
            s[i] = tmp[i]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Recursion

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        def reverse(l, r):
            if l < r:
                reverse(l + 1, r - 1)
                s[l], s[r] = s[r], s[l]

        reverse(0, len(s) - 1)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

3. Stack

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        stack = []
        for c in s:
            stack.append(c)
        i = 0
        while stack:
            s[i] = stack.pop()
            i += 1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Built-In Function

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

5. Two Pointers

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        l, r = 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$