Reverse Words in a String

I am a morning person and I do not seem to need eight hours of sleep a day. Earlier this morning (around 01:00 AM) I woke up and browsed the news on my phone. Most (never generalize) were not worth reading. They seem to have a catchy title, but after a few sentences a political message that had nothing to do with the main topic would come up. To top it off you have to reference the information from different sources due to the amount of fake news circulating in most (never say all) platforms.

My wife and I left a window in the kitchen open overnight. We both tend to sleep better with fresh air. Given that we live in the Twin Cities of Minneapolis and St. Paul, sooner rather than later we will have to keep the windows closed and the furnace on.

I just picked a random problem from LeetCode. Problem 151 Reverse Words in a String calls for reversing the order of words in a string. If interested please take a look at the description and spend a few minutes figuring out how to tackle the problem…

… OK, if you are still reading this post, chances are that you are interested. The idea is to put together a function that takes in a string and returns a string with the same words in reverse order. It appears that leading, in the middle, and trailing spaces should be removed.

When reversing order, I generally think of a stack. The idea is to push in what we need and then pop it generating the result.

I decided to solve this problem using Java and the VSCode IDE in a Windows 10 machine. I like to solve problems on my machine. That implies that we need to put together a test scaffolding. In this case such task seems to be relatively simple.

the sky is blue

main <<< s ==>the sky is blue<==
reverseWords <<< word ==>the<==
reverseWords <<< word ==>sky<==
reverseWords <<< word ==>is<==
reverseWords <<< word ==>blue<==
reverseWords <<< stack: [the, sky, is, blue]
main <<< reverseWords ==>blue is sky the<==


  hello world!  
  
main <<< s ==>  hello world!  <==
reverseWords <<< word ==><==
reverseWords <<< word ==><==
reverseWords <<< word ==>hello<==
reverseWords <<< word ==>world!<==
reverseWords <<< stack: [hello, world!]
main <<< reverseWords ==>world! hello<==
  
 
a good   example

main <<< s ==>a good   example<==
reverseWords <<< word ==>a<==
reverseWords <<< word ==>good<==
reverseWords <<< word ==><==
reverseWords <<< word ==><==
reverseWords <<< word ==>example<==
reverseWords <<< stack: [a, good, example]
main <<< reverseWords ==>example good a<==

LeetCode provides three examples. The examples provide a string which in some cases may have non-printable characters.

The test scaffolding seems to read in the string and display it. Note that we use a couple arrows to indicate the start and end of the provided string. It sees that the second string contains some leading and trailing spaces. The last example seems to contain some middle spaces.

The output shows the words in the input string. Note that some words contain a null string.

The contents of a stack are then displayed. It looks like we pushed into the stack most of the words as they were in the string.

Finally the reversed string is displayed.

    /**
     * Test scaffolding.
     */
    public static void main(String[] args) {
        
        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // **** read string ****
        String s = sc.nextLine();

        // **** close scanner ****
        sc.close();

        // **** display input string ****
        System.out.println("main <<< s ==>" + s + "<==");

        // **** reverse words in the string ****
        System.out.println("main <<< reverseWords ==>" + reverseWords(s) + "<==");
    }

We open a scanner, read the string in and close the scanner. We display the string to make sure we picked up the spaces. We then call the reverseWords() function and display the returned value.


    /**
     * Given an input string, reverse the string word by word.
     */
    static String reverseWords(String s) {

        // **** split string ****
        String[] words = s.split(" ");

        // **** used to reverse the order of the words ****
        Stack<String> stack = new Stack<String>();

        // **** push words into stack ****
        for (String word : words) {

            // ???? ????
            // System.out.println("reverseWords <<< word ==>" + word + "<==");

            // **** save word (if needed) ****
            if (!word.equals(""))
                stack.push(word);
        }

        // ???? ????
        // System.out.println("reverseWords <<< stack: " + stack.toString());

        // **** reverse the string ****
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {

            // **** append the next word ****
            sb.append(stack.pop());

            // **** append a ' ' (if needed) ****
            if (!stack.empty())
                sb.append(" ");
        }

        // **** return the reversed string ****
        return sb.toString();
    }

We start by splitting the words in the string into an array of words. We then create a stack which we will use to reverse the order of the words.

We traverse the words array only pushing into the stack the words that are not “”. This is a requirement for the problem.

We could use strings to reverse the order, but a StringBuilder provides better performance given that strings are immutable.

We now enter a look popping from the stack the word at the top and appending it to the string builder. We then check if we have more words to follow. If we do, we append a “ “; otherwise we do not.

When done we just return the contents of the string builder as a string.

It seems that LeetCode accepted the solution. If you just make sure the print comments are removed, you can just copy and paste the body of the function.

If you have a simpler and more elegant approach, please let me know.

The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 2214 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.