A in-place recursive solution to reverse a string

Question

I am learning recursion basics from leetcode's featured tutorial Recursion I

The first exercise is to reverse a string Reverse String - LeetCode

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"]

The accepted solution is

class Solution:
    def reverseString(self, s):
        """
        :type s: str
        :rtype: str
        """
        #base case
        if len(s) <= 1:
            return s
        #recur case 
        elif len(s) >= 2:
            n=len(s)
            return self.reverseString(s[n//2:])+self.reverseString(s[:n//2])

Two Problem with the solution:

1, Not modify in-place

2, It's expensive to recursively slicing a string.

As the first step to improve it, introduced parameters lo and hi to store index

class Solution:
    def reverseString(self, s, lo=0, hi=None):
        """
        :type s: str
        :rtype: None
        """
        if hi == None:
            hi = len(s)
      #base case
        if hi <= 1:
            return s

        #recur case 
        elif hi >= 2:
            mid = hi // 2
            left = self.reverseString(s, lo, mid)
            right = self.reverseString(s, mid, hi)
            return left + right               

It report error

　RecursionError: maximum recursion depth exceeded in comparison

---

Ran 1 test in 0.005s

Ｗhat' s the problem?

Answer 1

Here is my code in cpp. I have solve this using recursion but don't know how much effective solution this is? BTW below code is accepted.

void recursive(int start, int end, vector<char>& s) {
    
    if(start >= s.size()/2) {
        
        return;
    }
    recursive(start+1, end-1, s);
    swap(s[start], s[end]);
}


void reverseString(vector<char>& s) {
    
    int size = s.size();
    recursive(0, size-1, s);
}

Answer 2

Here is my solution. two pointer approach and binary search

s = ["h","e","l","l","o"]
print(s)
start = 0
end = len(s)-1
while start <= end:
    temp = s[start]
    s[start] = s[end]
    s[end] = temp
    start += 1
    end -= 1
print((s))

Answer 3

Here is an in-place recursive algorithm. In-place basically means don't use any auxiliary data structure. Remember we always use stack internally to perform recursion. Base case: if left >= right, do nothing. Otherwise: swap s[left] and s[right] and call helper(left + 1, right - 1).

To solve the problem, call helper function passing the head and tail indexes as arguments: return helper(0, len(s) - 1).

def reverseString(s):
    def helper(left, right):
        if left < right:
            s[left], s[right] = s[right], s[left]
            helper(left + 1, right - 1)
    helper(0, len(s) - 1)

Time-Complexity - O(n)

Auxiliary Space - O(n)

Answer 4

public class ReverseString {
    public void reverseString(char[] s){
        if(s.length<=1) {
            return;
        }
        int j=0;
        int i=s.length-1;
        while(i>j){
            char tmp;
            tmp=s[j];
            s[j]=s[i];
            s[i]=tmp;
            j++;
            i--;
        }
    }
}

Answer 5

Here is in place solution for this problem:

class Solution(object):
    def reverseString(self, s, left=0, right=0):
        if right == 0:
            right = len(s) - 1

        if left >= right:
            return

        temp = s[right]
        s[right] = s[left]
        s[left] = temp
        self.reverseString(s, left+1, right -1)

Answer 6

I am not sure why are you doing recursion. You can simply take two pointers, one at the start and one at the end of the string, start by swapping those characters, and move the pointers towards each other, until they cross, and then you break and return the reversed string.

class Solution:
    def reverseString(self, s):

        if len(s) <= 1: return s
        # The two pointers
        lo = 0
        hi = len(s) - 1
        # Iterate till both pointers cross
        while lo < hi:
            # swap the characters
            tmp = s[lo]
            s[lo] = s[hi]
            s[hi] = tmp
            # increment the pointers
            lo += 1
            hi -= 1
        return s


s = Solution()
print(s.reverseString(['h']))
print(s.reverseString(["h","e","l","l","o"]))
print(s.reverseString(["h","e","l","l","o","w","o","r","l","d"]))
#['h']
#['o', 'l', 'l', 'e', 'h']
#['d', 'l', 'r', 'o', 'w', 'o', 'l', 'l', 'e', 'h']

In addition, the recursive approach for the same is as follows

class Solution:
    def reverseString(self, s, lo=0, hi=None):

        #If one character or less in the string, return the string
        if len(s) <= 1:
            return s

        #The last index should be placed at the end of the string
        if hi == None:
            hi = len(s) - 1

        #If the two indexes cross, return the string
        if hi < lo:
            return s

        #swap the low and high characters
        tmp = s[lo]
        s[lo] = s[hi]
        s[hi] = tmp
        #Recursively call the function
        return self.reverseString(s, lo + 1, hi - 1)

s = Solution()
print(s.reverseString(['h']))
print(s.reverseString(["h","e","l","l","o"]))
print(s.reverseString(["h","e","l","l","o","w","o","r","l","d"]))
#['h']
#['o', 'l', 'l', 'e', 'h']
['d', 'l', 'r', 'o', 'w', 'o', 'l', 'l', 'e', 'h']

Answer 7

To do this without space, you need to swap. You can't add array slices. Instead of splitting the indexes in the middle, which will never let you swap opposite pairs (expect in the base case).

You can see it, if you imagine the recursion visually. You start with a list like:

1, 2, 3, 4
^        ^ <-- these need to swap in a reverse

But after your first recursive call you split this into:

---- | ----
1, 2   3, 4
^         ^  <-- these still need to be swapped, bu when?

Now branch one has no way to get at the 4 in branch two to swap unless there's a non-obvious way to do it as the recursion unwinds.

You can instead (much more easily) walk you indexes in from both ends and swap as you go. Then your base case is just when they meet in the middle:

class Solution:
    def reverseString(self, s, lo=0, hi=None):
        if hi == None:
            hi = len(s) - 1

        if hi <= lo:
            return s

        s[lo], s[hi] = s[hi], s[lo]
        return self.reverseString(s, lo + 1, hi - 1)


s = Solution()
s.reverseString([1, 2, 3, 4])
# [4, 3, 2, 1]
s.reverseString([1, 2, 3, 4, 5])
#[5, 4, 3, 2, 1]