Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

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

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 trailingspaces.

How about multiple spaces between two words?

  • Reduce them to a single space in the reversed string.
public static String reverseWords(String s){
    StringTokenizer strTok = new StringTokenizer(s, " ");
    Stack<String> stack=new Stack<String>();
    StringBuilder buff=new StringBuilder();
    while(strTok.hasMoreElements()) {
        String str = (String)strTok.nextToken();
        if(!str.equals("")) stack.push(str);
    }
    while(!stack.isEmpty()){
        buff.append(stack.pop()); 
        if(!stack.isEmpty()) buff.append(" ");
    }
    return buff.toString();
 }
share|improve this question
1  
There's a (little known) class in the Java class libraries that's meant for these problems. BreakIterator: docs.oracle.com/javase/7/docs/api/java/text/BreakIterator.html The javadoc even has an example that does almost exactly what you want. –  tom Mar 9 at 12:36
    
@tom: I'd love to see an example for the problem with BreakIterator (as an answer:) –  palacsint Mar 9 at 13:35
    
Is their something I am missing? Use .toCharArray() or .split(String s). –  horvste Mar 9 at 22:24

4 Answers 4

up vote 15 down vote accepted
  1. Stack seems more or less deprecated. Javadoc says the following:

    A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

    I guess an ArrayDeque is a good choice here.

  2. It's seems that StringTokenizer is also deprecated. Javadoc says the following:

    StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead.

  3. I'd rename

    • buff to result
    • stack to words
    • str to word

    to describe their purpose. It would be easier to read and help understanding code.

  4. You could move the declaration of buff right before the second while loop.

    StringBuilder buff = new StringBuilder();
    while (!stack.isEmpty()) {
        buff.append(stack.pop());
        if (!stack.isEmpty())
            buff.append(" ");
    }
    

    Try to minimize the scope of local variables. It's not necessary to declare them at the beginning of the method, declare them where they are first used. (Effective Java, Second Edition, Item 45: Minimize the scope of local variables)

  5. if(!str.equals(""))
    

    You could use String.isEmpty() here. It's easier to read since it says in a similar language to English what does this condition do.

  6. if(!str.equals("")) stack.push(str);
    

    According to the Code Conventions for the Java Programming Language,

    if statements always use braces {}.

    Omitting them is error-prone. I've found the one-liner above hard to read because if you scan the code line by line it's easy to miss that at the end of the line there is a statement (push).

  7. It's good to know that there is a similar function in Apache Commons Lang: StringUtils.reverseDelimited. You can check the implementation online for other ideas.

    (See also: Effective Java, 2nd edition, Item 47: Know and use the libraries The author mentions only the JDK's built-in libraries but I think the reasoning could be true for other libraries too.)


Here is the modified code with the Deque and other suggestions:

public static String reverseWords(String input) {
    Deque<String> words = new ArrayDeque<>();
    for (String word: input.split(" ")) {
        if (!word.isEmpty()) {
            words.addFirst(word);
        }
    }
    StringBuilder result = new StringBuilder();
    while (!words.isEmpty()) {
        result.append(words.removeFirst());
        if (!words.isEmpty()) {
            result.append(" ");
        }
    }
    return result.toString();
}
share|improve this answer
    
Very minor point, but result.append(" ") is more expensive than result.append(' '). Compare: append(char) with append(String) - if you are only appending a single char, it increments only one char. Strings you need to find their size, get the backing array, etc... –  MichaelT Mar 10 at 2:27
1  
good answer. i would choose to use a variable name like wordSet or wordList instead of words because its hard to distinguish words from word in the code –  Arvind Sridharan Mar 14 at 3:27

I would simply use split and than iterate the resulting array backwards to create the result:

@Nonnull
public static String reverse(@Nonnull final String sentence) {
  final StringBuilder result = new StringBuilder();
  final String[] words = sentence.split("\\s+");      
  for (int i = words.length - 1 ; 0 <= i; i--) {
    result.append(words[i]).append(' ');
  }
  return result.toString().trim();
}

P.s. I think a Stack and a StringTokenizer are a bit heavy stuff for this and without them the implementation is still quite slim.

share|improve this answer
    
i >= 0 I think. –  Anirban Nag Mar 9 at 15:56
    
@tintinmj: You are right, fixed it –  MrSmith42 Mar 9 at 18:41

Using a Stack and StringTokenizer seems to be a bit of an overkill here. A more simplified version could be written like this:

public static String reverse(final String input) {
  Objects.requireNonNull(input);
  final StringBuilder stringBuilder = new StringBuilder();
  for (final String part : input.split("\\s+")) {
    if (!part.isEmpty()) {
      if (stringBuilder.length() > 0) {
        stringBuilder.insert(0, " ");
      }
      stringBuilder.insert(0, part);
    }
  }
  return stringBuilder.toString();
}

This uses the ability of split() to take a String apart based on a given Regex. So the string is split based on a sequence of one or more white-spaces, which matches your initial requirement. Note that split will return an empty array in case input is an empty string.

The for-each loop then works through the array and inserts the part at the beginning of the stringBuilder (except for the first time), which will effectively reverse the array. Most people would probably use a reverse for(i...) loop here, but because this is a code review I try to be extra correct, and this is the safer version: You cannot cause ArrayIndexOutOfBoundsExceptions with for-each.

Any leading/trailing white-space will cause empty parts to appear in the splitted list, so there is a check for it in the loop. I use isEmpty() here, as this is in general safer (as in: less chance to do typos) than length() > 0 and benefits from potential, internal optimizations of String in terms of execution speed. You could call trim() beforehand, but this would cause some unnecessary String operations and creations, so this version is more efficient.

Please also note the check for null at the beginning. The code would otherwise throw when trying to split on null, but it is considered good practice to check before-hand, as theoretically (not in this code but in other) you otherwise might leave the system in an undefined state.

I also make use of final, which allows some compiler optimizations and prevents you from some basic coding mistakes, which is considered good practice.

Testing

It is always a good idea to do some quick testing of the functionality including the basic edge-cases, so here it is:

To check whether or not I do correct white-space removal, I change stringBuilder.insert(0, " ") to stringBuilder.insert(0, "+") for the test, to make the white-space visible.

When testing with System.out.println(reverse("the sky is blue")); the result is: blue+is+sky+the The initial requirement is met.

When testing with System.out.println(reverse(" \t the sky is\t blue ")); the result is: blue+is+sky+the Leading, trailing and in-between white-spaces are correctly removed.

When testing with reverse("") the result is an empty String as expected.

When testing with reverse(null) a NullPointerException is thrown at the beginning of the function.

share|improve this answer
    
When doing inserts and appends with a single character, the code for insert(int,char) is less expensive than for insert(int, String) - chars are always a single unit while Strings you need to find the size of the String, get the backing array, check for null, etc. –  MichaelT Mar 10 at 2:30
    
That's true and a good point. But also only relevant if the method above is run like a million times per second. ;) –  TwoThe Mar 10 at 11:47
    
Using the character version rather than the String version of the call, while not something that is critical to this application is a good thing to keep in mind and make part of one's standard "this is how you do it" and done that way without thinking if you should use a " " or ' ' in the future. While the performance likely isn't an issue here, following the best practices and writing the most efficient code up front begins with a single code review. –  MichaelT Mar 10 at 14:30

This type of question is always interesting, because I always feel there is the easiest, and the best way to do things. Easiest often relies on using native mechanisms for the work. The best, I feel, is often to use primitives and to do as few object creations as possible.

Here are the two candidate solutions I can suggest for the easiest/best. The Easiest uses the String.split() method, but unlike other solutions suggested here, it is purely 'additive'. No inderting things in the middle, and no inserting extra stuff which gets deleted. It also does some input validation. 'Trimming' the value before the split is important....

The 'best' option is plain O(n) performance (StringBuilder.insert(...) used in some solutions is not going to produce an overall O(n) solution). This suggested solution does not create all the intermediate String objects that the other solutions create, and it uses O(1) extra memory space.

public static void main(String[] args) {
    String[] input = {"", null, "a", "this is", "this    is", " this is "};
    for (String in : input) {
        System.out.println("Split: -> |" + reverseString(in) + "|");
        System.out.println("Array: -> |" + reverseStringFP(in) + "|");

    }
}


private static final String reverseString(String input) {
    if (input == null) {
        return null;
    }
    String[] parts = input.trim().split("\\s+");
    if (parts.length == 0) {
        return "";
    }
    StringBuilder sb = new StringBuilder();
    sb.append(parts[parts.length - 1]);
    for (int i = parts.length - 2; i >= 0; i--) {
        sb.append(" ").append(parts[i]);
    }
    return sb.toString();
}

private static final String reverseStringFP(final String input) {
    if (input == null) {
        return null;
    }
    if (input.isEmpty()) {
        return "";
    }
    final char[] inchar = input.toCharArray();
    // + 1 to allow for a temporary trailing space
    final char[] outchar = new char[inchar.length + 1];
    int outpos = 0;
    int wordend = inchar.length - 1;
    while (wordend >= 0) {
        while (wordend >= 0 && inchar[wordend] == ' ') {
            wordend--;
        }
        int wordstart = wordend;
        while (wordstart > 0 && inchar[wordstart - 1] != ' ') {
            wordstart--;
        }
        if (wordstart >= 0) {
            int len = wordend - wordstart + 1;
            System.arraycopy(inchar, wordstart, outchar, outpos, len);
            outpos += len;
            outchar[outpos++] = ' ';
            wordend = wordstart - 1;
        }
    }
    if (outpos > 0) {
        // deal with trailing space
        outpos--;
    }
    return new String(outchar, 0, outpos);
}
share|improve this answer
    
+1. A minor note: I'd use a variable instead of the comment: boolean hasTrailingSpace = outpos > 0; if (hasTrailingSpace) ... –  palacsint Mar 9 at 13:33
    
What does FP stand for in reverseStringFP? –  Anirban Nag Mar 9 at 16:02
    
@tintinmj - First Principles - no reference to any other libraries ... how I imagine a basic implementation would do it. –  rolfl Mar 9 at 16:06
    
Hmmm but aren't you using System and String? –  Anirban Nag Mar 9 at 16:10
    
Where people draw the line is their choice. I am not using anything outside of the Java language specification and java.lang.* (i.e. I am not using regex, Collections, etc. which would, themselves, have to iterate character-by-character over the value) –  rolfl Mar 9 at 16:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.