DEV Community

Mridu Bhatnagar
Mridu Bhatnagar

Posted on

2

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.

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay