Reverse Words in a String Algorithm

Today we will try to solve “Reverse Words in a String” task for leetcode.

Task description:

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

Stop and think…

You can see that is easy task. I think there are a lot ways to solve this task I will provide just a one. So, what is the solution can be ?

For example:

–  we can create new one string and goes through input string from end to start  and copy all elements from input to created string, can work ? Why not …

– we can create four indexes like next

        int firstWordStart = 0;
        int firstWordEnd = 0;
        int lastWordStart = s.length()-1;
        int lastWordEnd = s.length()-1;

and work with these indexes, till

firstWordEnd < lastWordStart

but we should manage string with shifting all words because length of first and last words can be diff, So, That is hard but can be solution with swap in place.

– we can use recursion and if we found whitespace start next recursion cycle with string without first word and after recursion add first word to the end (it’s like Reverse LinkedList {Recursion implementation} ), that is good solution, but can be problem with stack memory.

– we can split words by whitespace char ” ” and reverse all words in splitted array after that create result string from array, that solution like first but more elegant for my point of view, so, I am going to implement the solution (leetcode accepted it, so, it’s right 🙂 )

public String reverseWords(String s) {
       s = s.trim();
       String [] data = s.split(" ");
       int lastIndex = data.length-1;
       for(int i = 0; i < data.length/2; i++){
        swap(data, i, lastIndex);
        lastIndex--;
       }
       return returnString(data);
    }
 
    void swap(String[] data, int startIndex, int endIndex){
        String temp;
        temp = data[endIndex];
        data[endIndex] = data[startIndex];
        data[startIndex] = temp;
    }
 
    String returnString(String [] data){
        StringBuilder result = new StringBuilder();
        for(String datum:data){
            if(datum!=null && datum.trim().length()!=0)
                result.append(datum).append(" ");
        }
        return result.toString().trim();
    }

So, we have 3 methods, first is main and executing main logic.

Next one swap, swap is very easy, just swapping elements in array.

Last one is reversed string creator.

So, that is all…

Cheers !