Leetcode – Reverse String Solution in Python

Spread the love

In this extensive article, we will delve into a classic problem on LeetCode known as the ‘Reverse String’. This problem is a foundation for understanding string manipulation and various algorithms. We will discuss the problem statement, explore different methods to solve it, and evaluate their time and space complexities.

Introduction

Let’s begin by examining the problem statement:

Write a function that reverses a string. The input string is given as an array of characters s. Do not return anything, modify s in-place instead.

Example:

Input: s = [“h”,”e”,”l”,”l”,”o”]

Output: [“o”,”l”,”l”,”e”,”h”]

Understanding the Problem

The problem is straightforward: We need to reverse the input array of characters s in-place. The challenge here is to do this without using extra space for another string or array.

Approach 1: Two Pointers

A standard approach to solve this problem is using two pointers. One pointer starts at the beginning of the array, and the other at the end. We then swap the elements at these two pointers, move them toward each other, and continue until they meet or pass each other.

  1. Initialize two pointers: left at 0 and right at the end of the array.
  2. While left is less than right: a. Swap s[left] and s[right]. b. Increment left and decrement right.
def reverseString(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left, right = left + 1, right - 1

Time Complexity:

O(n) – We traverse half of the array, and swapping takes constant time.

Space Complexity:

O(1) – We only use two pointers, so we do it in constant space.

Approach 2: Recursion

We can also solve this problem using recursion. Recursively reverse the subarray from left+1 to right, and then place the left item at the right position.

  1. Base case: if left >= right, return.
  2. Swap s[left] and s[right].
  3. Recursively call the function with left+1 and right-1.
def reverseString(s, left=0, right=None):
    if right is None:
        right = len(s) - 1

    if left >= right:
        return
    
    s[left], s[right] = s[right], s[left]
    
    reverseString(s, left + 1, right - 1)

Time Complexity:

O(n) – Similar to the two pointers approach, each element is swapped once.

Space Complexity:

O(n) – Due to the recursive stack. Each recursive call adds a layer to the stack.

Approach 3: Using Python’s Slicing

Though not the most efficient in terms of algorithmic complexity, Python’s slicing feature can be used for its brevity and ease of use.

def reverseString(s):
    s[:] = s[::-1]

Time Complexity:

O(n) – We create a new reversed array and then copy it back to s.

Space Complexity:

O(n) – A new array is created by slicing.

Conclusion:

The Reverse String problem on LeetCode is a fundamental problem for anyone seeking to understand string manipulation and basic algorithms. Through various approaches ranging from the efficient two pointers method to the more Pythonic slicing method, this problem teaches the importance of understanding the nuances and tools of the language you are working with. While the two pointers approach is efficient and widely applicable in different languages, Python’s slicing can be handy for rapid development or scripting. The recursive approach, although not space-efficient in this scenario, is a good exercise to understand recursion. This problem is exemplary of the various ways a simple task can be approached algorithmically, and is foundational in building strong problem-solving skills.

Leave a Reply