Given an input String, we would like to output a new String with reversed order of words, while maintaining the order of the characters within each word.

We should also handle the unnecessary whitespace in the String.

Sample Input 1

Input: “Just Do It”

Output: “It Do Just”

Sample Input 2

Input: “ Just Dot It ”

Output”: “It Do Just”

Output String should remove the start and end whitespaces.

Sample Input 3

Input: “Just Dot It”

Output”: “It Do Just”

Output String should remove any extra whitespaces.

Sample Input 4

Input: “ ”

Output: “”

Input String containing only whitespace should return whitespace removed output String.

Approach 1

The first solution which came to mind is char by char iterations to build an array of words and then reverse iterate on the array of words to build a reverse String. The steps are given below:

1. Create and initialize an empty String variable reverseWords.
2. Create an array of Strings (say words) to store words.
3. Create and Initialise an empty String variable called currentWord. We will use it to hold the partial word while traversing input String char by char.
4. Traverse the input string char by char.
   1. If the current char is whitespace and currentWord is not empty, add currentWord in words array and reinitialize the currentWord as an empty String.
   2. If the current char is not whitespace, append the char to currentWord
5. If words array length is greater than 0, iterate words from reverse and for each word
   1. if reverseWords is not empty, append whitespace and then append the current word
   2. if reverseWords is empty, then append the current word
6. return reverseWords

Implementation in Java:

import java.util.ArrayList;
import java.util.List;

public class ReverseString {

	public static String reverse(String input) {
        StringBuilder reversedString = new StringBuilder();
        List<String> words = new ArrayList<>();
        StringBuilder currentWord = new StringBuilder();

        for (Character currentChar : input.toCharArray()) {
            if (Character.isWhitespace(currentChar) && (currentWord.length() > 0)) {
                words.add(currentWord.toString());
                currentWord = new StringBuilder();
            } else if (!Character.isWhitespace(currentChar)) {
                currentWord.append(currentChar);
            }
        }

        if (currentWord.length() > 0) {
            words.add(currentWord.toString());
        }
        for (int i = words.size() - 1; i > -1; i--) {
            if (reversedString.length() > 0) {
                reversedString.append(" ");
            }
            reversedString.append(words.get(i));
        }

        return reversedString.toString();
    }

}

In terms of cyclomatic complexity, O(n) Time and O(n) Space where n is the number of characters in the input String.

Approach 2

We can also use the programming language’s inbuilt split function to split the input String on whitespace to obtain the array of words and the rest of the logic will be the same as the earlier approach along with cyclomatic complexity.

Java Implementation using split function:

import java.util.ArrayList;
import java.util.List;

public class ReverseString {
	public static String reverseUsingSplit(String input) {
        StringBuilder reversedString = new StringBuilder();
        List<String> words = List.of(input.split(" "));

        for (int i = words.size() - 1; i > -1; i--) {

            if (words.get(i).isEmpty()) continue;

            if (reversedString.length() > 0) {
                reversedString.append(" ");
            }

            reversedString.append(words.get(i).trim());
        }

        return reversedString.toString();
    }
}

Summary

In this article, we solve the “Reverse words in a String” problem using two approaches. We can use any one of them as the time and space complexity is linear for both.

For complete source code and unit tests please visit Github Repo.