In this tutorial we are going to solve Leetcode Problem number 344. Reverse String

Problem statement:

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Thought process:
There are two ways to solve this problem:

• Recursive way

• Iterative way

But both of the ways will include using two pointers. Since we have to modify array in-place.

But where will you assign those two pointers 🤔🤔? Lets try to visualize it with a very small input: Consider you have input as : ["h", "e"] (the input is given as a list) Here you just need to swap "e" and "h", to get the reverse. So, you need one pointer at "h" and another at "e".

Now lets take a slightly bigger input: ["h", "e", "l", "l" ] (😈😈☠)

Don't worry it is not as scary as the word "hell", lol.

Here, we need to swap "h" with "l" followed by "e" with another "l"

So again we will have to point our first pointer at "h" and last pointer at "l" After swapping them we will move the first pointer towards "e" and last pointer towards "l" and swap them as well.

Now what? you know you are done reversing your string, but we need to figure out where we can stop. If we just keep on moving then eventually our first pointer will keep on incrementing and we will get "index out of range" error! damn!.

But everything is in front of our eyes 👀. At our last stage, first pointer was at "e" that is index "1" and last pointer was at "l" which is index "2". If we move our indexes again then we will have first pointer at index "2" and last pointer at index "1". But in previous steps we had last pointer > first pointer. So we know we have to stop when our first pointer becomes greater than last pointer.

We did most of our job, now its time to write our code! But before that go through the images below to get the picture of what is happening.

Lets proceed with our code (Note that given length of input list is greater than 1, so we do not need to handle the case of empty list) And the case when length of input is 1 will also be handled by our code Example: input is ["h"] first pointer at index 0 last pointer is also at last index 0(length of s - 1--> 0) so we will just swap them; although that is unnecessary! So we will just add a condition:

if len(s) == 1:
    return s

If you understood the idea, then you can jump in to the below recursive code (after you try it on your own first!😒😂 ):

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        if len(s) == 1:
            return s
        #initialize first pointer at index 0
        first = 0
        #intialize last pointer at last index
        last = len(s) - 1
        #we have to do it in place so use pointers 
        def lets_reverse(first, last, s):    
            if first > last:
                return
            s[last], s[first] = s[first], s[last]
            lets_reverse(first+1, last-1, s)

        lets_reverse(first, last, s)

We just assigned two pointers and checked for the condition if first > last. If that is not the case then we just swap and call the function after incrementing our first pointer by 1 and decrementing last pointer by 1.

Writing this code iteratively is also similar. The only thing is you will have to use while loop to check for the condition when to stop.

Below is the code to solve the above problem iteratively:

class Solution:

    def reverseString(self, s: List[str]) -> None: 

        """
        Do not return anything, modify s in-place instead.
        """
        first = 0 
        last = len(s) - 1 
        while first < last:
            s[first],s[last] = s[last], s[first] 
            first +=1 
            last -= 1
        return

This was it! Great job on solving another recursion problem 🥳🥳 If you like this tutorial and want to move ahead with this series on recursion, follow me on hashnode as well as on twitter to show your support 😀