Saturday, May 5, 2018

How to reverse the sequence of words in a given string


Unlike C/C++, Java Strings are immutable, hence inline operations within a string are not possible. In fact, each time we make a modification to string, a new string literal is created and stored in String Pool internally. Probably doing manipulations using char array can give better performance.

Pseudo Code for Java

  1. Split the String into words using white space as separator
  2. Reverse the collection consisting of words
  3. Join the collections of word back into string
Java 8 Program to reverse the order of words in String
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ReverseWords {

    public String reverseJava8Style(String input){
        List<String> list = Arrays.asList(input.split("[\\s]"));
        Collections.reverse(list);
        return String.join(" ", list);
    }
}


public class ReverseWordsTest {
    ReverseWords utils = new ReverseWords();

    @Test
    public void reverseJava8Style() {
        String reverseJava8Style = utils.reverseJava8Style("My Name is Tanishq");
        assertThat(reverseJava8Style, equalTo("Tanishq is Name My"));
    }

Time Complexity

Complexity corresponding to each pseudo step:
  • Step 1. O (n) where n is number of characters in string
  • Step 2. O (k) where k is the number of words. k < n
  • Step 3. O (K) where k is number of words, k < n
Overall time complexity is O(n).
If it was C/C++, we could have used a better approach that replaces everything inline without any additional memory:
  1. Reverse the entire string
  2. Reverse the characters inside each word
  3. Print the string
But this approach will not work due to Immutable nature of Strings in java, thus would generate too many string literals. So the second approach is not discussed here.

No comments:

Post a Comment

Your comment will be published after review from moderator