Reverse a string word by word

Question

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();
 }

Answer 1

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();
}

Answer 2

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.

Answer 3

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.

Answer 4

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);
}