2024-06-02: Leetcode Daily Challenge 344. Reverse String

Level: easy
Requirements:

Write a function that reverses a string. The Input String is given as an array of charater `s`. You must do this by modifying the input array **in-place** with `O(1)` extra memory.

The First Intuition

The first intuition would be "iterate the given array from the end to the beginning and store each element in the new array. Finally, the new array will be assigned to the array s". This method seems pretty simple and will work surely. However, it is not really a in-place algorithm.

Improvement: Two Pointers Method

To make the algorithm a really in-place, two pointers method will be used, where

• assign two pointers, l and r, which store the index value of each end, i.e. the left end and the right end.
• By incrementing l and decrementing r until l are the same as r or l is greater than r.
• While iterating, we swap each element in the given array of character.

void reverseString(vector<char>& s) {
    int l = 0;
    int r = s.size() - 1;

    while (l < r){
        char tmp = s[l];
        s[l] = s[r];
        s[r] = tmp;


        ++l;
        --r;
    }

}

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

        while l < r:
            tmp = s[l]
            s[l] = s[r]
            s[r] = tmp

            l += 1
            r -= 1

Time Complexity: O(N)
Space Complexity: O(1)