Tuesday, 28 July 2015

Reverse string using recursion

There are number of ways to reverse a string. I am going to explain three approaches here.

Approach1
In first approach, we divide the string into two parts, recursively, until string has single character and combine them in reverse.

Following snippet reverse string using approach1.

private static String reverseApproach1(String str) {
 if (str.length() == 1)
  return str;

 int mid = str.length() / 2;
 return reverseApproach1(str.substring(mid, str.length())) + ""
   + reverseApproach1(str.substring(0, mid));
}

Approach2
Following snippets also used to reverse string.

private static String reverseApproach2(String str) {
 if (str.length() == 1)
  return str;
 return reverseApproach2(str.substring(1)) + str.charAt(0);
}

As you observe the code, every time I am omitting first character and appending it to the recursive function.

Approache3
Following algorithm uses character array to reverse a string.

private static void reverseApproach3(char[] array, int start, int end) {
 if (start > end)
  return;

 char temp = array[start];
 array[start] = array[end];
 array[end] = temp;

 reverseApproach3(array, ++start, --end);
}
Find complete working application.

import java.util.Objects;

public class StringReverse {

 public static String reverseStringApproach1(String str) {
  Objects.nonNull(str);
  return reverseApproach1(str);
 }

 private static String reverseApproach1(String str) {
  if (str.length() == 1)
   return str;

  int mid = str.length() / 2;
  return reverseApproach1(str.substring(mid, str.length())) + ""
    + reverseApproach1(str.substring(0, mid));
 }

 public static String reverseStringApproach2(String str) {
  Objects.nonNull(str);
  return reverseApproach2(str);
 }

 private static String reverseApproach2(String str) {
  if (str.length() == 1)
   return str;
  return reverseApproach2(str.substring(1)) + str.charAt(0);
 }

 public static String reverseStringApproach3(String str) {
  Objects.nonNull(str);
  char characters[] = str.toCharArray();
  reverseApproach3(characters, 0, str.length() - 1);
  return new String(characters);
 }

 private static void reverseApproach3(char[] array, int start, int end) {
  if (start > end)
   return;

  char temp = array[start];
  array[start] = array[end];
  array[end] = temp;

  reverseApproach3(array, ++start, --end);
 }

}
Following is the junit test cases for above class.

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class StringReverseTest {

 @Test
 public void test1() {
  assertEquals(StringReverse.reverseStringApproach1("abcde"), "edcba");
  assertEquals(StringReverse.reverseStringApproach1("abcd"), "dcba");
  assertEquals(StringReverse.reverseStringApproach1("ab"), "ba");
  assertEquals(StringReverse.reverseStringApproach1("a"), "a");
 }

 @Test(expected = NullPointerException.class)
 public void test2() {
  StringReverse.reverseStringApproach1(null);
 }

 @Test
 public void test3() {
  assertEquals(StringReverse.reverseStringApproach2("abcde"), "edcba");
  assertEquals(StringReverse.reverseStringApproach2("abcd"), "dcba");
  assertEquals(StringReverse.reverseStringApproach2("ab"), "ba");
  assertEquals(StringReverse.reverseStringApproach2("a"), "a");
 }

 @Test(expected = NullPointerException.class)
 public void test4() {
  StringReverse.reverseStringApproach2(null);
 }

 @Test
 public void test5() {
  assertEquals(StringReverse.reverseStringApproach3("abcde"), "edcba");
  assertEquals(StringReverse.reverseStringApproach3("abcd"), "dcba");
  assertEquals(StringReverse.reverseStringApproach3("ab"), "ba");
  assertEquals(StringReverse.reverseStringApproach3("a"), "a");
 }

 @Test(expected = NullPointerException.class)
 public void test6() {
  StringReverse.reverseStringApproach3(null);
 }
}




No comments:

Post a Comment