Day-14 Reverse String

Background

This problem statement is a part of Leetcode's learning card Array and Strings. Under the sub-heading two pointer technique.

Problem Statement

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

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ASCII characters.

Example 1

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2

Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Solution Approach 1

Use python built-in methods. There are two ways of doing the same. Suppose s in the initial list. Then s.reverse() could be done or s[::-1] can be done.

Had reaching the solution by using the built-in methods been the aim. Probably the whole exercise would not have been worth the effort.

Solution Approach 2

1. Iterate over the list.
2. Swap the first element with the last element.
3. The list would be completely reversed when we are at the mid of the list.
4. When the index of the current element is equal to mid of the list. Break.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        for x in range(0, len(s)):
            if x == int(len(s)/2):
                break
            else:
                temp = s[x]
                s[x] = s[len(s)-x-1]
                s[len(s)-x-1]=temp

Learnings

1. Time complexity - O(n), Space complexity - O(1).

A more elegant approach

Solution approach 3

1. Keep two variables. One at the starting of the list at index 0. Another at the end of the list. Index len(L)-1.
2. Keep swapping the elements until both the variables reach the mid of the list.

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

Learnings

1. The solution is still time complexity O(n) and space complexity O(1).
2. Two pointer technique. Though in python there is no concept of pointer as such.
3. Built-in reverse method is also implemented the same way.