Write a program to reverse a string

Posted by N.K. Chauhan on Mar 31, 2024

A string s is given, the task is to reverse it using recursion.

Example 1: Reverse "abcd"

Input: abcd
Output: dcba

Example 2: Reverse "xyz"

Input: xyz
Output: zyx


Solutions

Method 1: Recursion

Here we will swap first and last characters and recur for remaining substring. If string has only one character it is already reversed, this will make the base condition.

package com.cb.recursion;

/*
 * Recursion
 * */
public class ReverseAString {

    // abc abcd
    public static String reverse(String s, int startIndex, int endIndex) {
        if (startIndex >= endIndex)
            return s;
        String s1 = swap(s, startIndex, endIndex);
        return reverse(s1, startIndex + 1, endIndex - 1);
    }

    private static String swap(String s, int i, int j) {

        char[] chars = s.toCharArray();

        char c = chars[i];
        chars[i] = chars[j];
        chars[j] = c;

        return new String(chars);
    }

    public static void main(String[] args) {

        String s = "abc";
        System.out.println(reverse(s, 0, s.length() - 1));

        String s1 = "abcd";
        System.out.println(reverse(s1, 0, s1.length() - 1));
    }
}
cba
dcba

Complexity

In every fn call, we are increasing start index and decreasing end index, that means fn is called n/2 or n/2+1 times for a string of size n; so Time Complexity is O(n).

We are also storing startIndex and endIndex in every call, so Space Complexity is 2n or O(n).

Related


Print numbers from a given number to 0

Program for printing nth Fibonacci Number

Calculate the Power of a Number (n^p)

Print numbers from 0 to a given number

Print spelling for a given number

Count ways to reach the nth stair

Program to solve "Tower of Hanoi" problem

Check if an integer array is sorted or not

Calculate factorial of a given number

Sum of the digits of a given number