Reverse Words in a String

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

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

click to show clarification.

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.

Simple question, scan from the end to the start, push all the characters into a stack, once met with a ” “, pop everything out from the stack and append it to the result string, adding ” ” to the end when stack was empty. Keep scanning and start pushing the character into stack again when met with a non-” ” character. Notice that when finished and stack is not empty, need to pop the last word from stack.

public class Solution {
    public String reverseWords(String s) {
        s = s.trim();//remove heading or trailing string
        Stack<Character> word = new Stack<Character>();
        StringBuilder result = new StringBuilder();
        for(int i = s.length()-1; i>=0; i--) {
            if (s.charAt(i) != ' ') {
                    word.push(s.charAt(i));
            }
            else {
                if (word.isEmpty())
                    continue;
                while(!word.isEmpty())
                    result.append(word.pop());
                result.append(" ");
                word = new Stack<Character>();
            }
        }
        //last word push
        while(!word.isEmpty())
            result.append(word.pop());
        return new String(result);
    }
}

Do it without using stack

public class Solution {
    public String reverseWords(String s) {
       s=s.trim();
       if (s.length() == 0)
           return "";
       StringBuilder tmp = new StringBuilder();
       for (int i = s.length()-1; i >= 0; i--) {
           if (s.charAt(i) != ' ') {
               int j = i;
               while(j >= 0 && s.charAt(j) != ' ') {
                   j--;
               }
               if (j >= 0)
                tmp.append(s.substring(j+1, i+1) + " ");
               else 
                tmp.append(s.substring(0, i+1)); //last word
               i = j;
           }
       }
       return new String(tmp);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s