Reversing the words order of a string

Question

A couple of weeks I had a coding interview and the problem to solve was very simple: reverse the words order of a string. What did I do wrong here?

public static String reverse(String phrase) {
 String[] words = phrase.split(" ");
 StringBuffer sb = new StringBuffer();
 for (String word : words) {
 String reversed = new String();
 for (int j = word.length() - 1; j >= 0; j--) {
 reversed += word.charAt(j);
 }
 sb = sb.append(reversed).append(" ");
 }
 return sb.toString().substring(0, sb.toString().length() - 1);
 }

• Hovercraft Full Of Eels: String reversed = new String(); this doesn't look good. Why are you doing this when you're already using a StringBuffer (which should be a StringBuilder, by the way)? When is it ever appropriate to use new String()??
• markspace: Also, sb = sb.append(... it is unnecessary to assign the StringBuilder reference. Two unforced errors, makes it look like you don't understand objects and references.
• Hovercraft Full Of Eels: In the StringBuffer API: As of release JDK 5, this class has been supplemented with an equivalent class designed for use by a single thread, StringBuilder. The StringBuilder class should generally be used in preference to this one, as it supports all of the same operations but it is faster, as it performs no synchronization.
• markspace: One more thing: you extract a String from sb (at the return) and then immediately call substring() on that string. Strings are immutable, and this forces another buffer copy. You should have reduced the length of the string builder first, then called toString().

Answer 1

The main reason why you fail may be because your code reverse the entire sentence while only the order of the words must be reversed; Hello the world should be world the hello. If you want to reverse the whole string, there is StringBuilder.html#reverse()

That put aside. Some problems I see is the usage of StringBuffer which is slower but synchronized. There is also this new String() in your loop which is useless because you can already use sb.append. And there is this ugly string building at the end where sb.toString() is abused while sb.delete can do it.

---

For the fun I made mine which revert the words by traversing the char sequence from the end and insert the character at a given index. The index is changed when a space is found to insert at the end of the new string : https://github.com/gervaisb/stackexchange-codereview/blob/q184229/src/main/java/q184229/Sentence.java

final StringBuilder target = new StringBuilder(value.length());
for (int i=value.length()-1, at=0; i>-1; i--) {
 char character = value.charAt(i);
 if ( Character.isWhitespace(character) ) {
 target.append(character);
 at = target.length();
 } else {
 target.insert(at, character);
 }
}

Answer 2

Your current solution looks to be too complex. If all you need to do is swap the order of words, Strings that are separated by white space, then why not simply do this:

• Use String#split("\\s+") to split the input text into an array of words -- of Strings split greedily by white-space
• Iterate through this array backwards in a simple for loop
• Add these Strings to a StringBuilder (not a StringBuffer which has unnecessary overhead of thread-safety -- we're doing this in only one thread)
• Avoiding use of new String(...), it's almost never necessary to use this, and there is a down-side to its use, including avoiding appropriate and efficient use of the String-pool.
• And then return.

e.g., something as basic as:

public static String reverseWords(String inText) {
 StringBuilder sb = new StringBuilder();
 String[] tokens = inText.split("\\s+");
 for (int i = tokens.length - 1; i >= 0; i--) {
 sb.append(tokens);
 if (i != 0) {
 sb.append(" ");
 }
 } 
 return sb.toString();
}

• Eliú Abisaí Díaz Vásquez: I like your solution but what about String.split method? the interviewer didn't like it and asked me how can I avoid to create several copies of the same string when using String.split and I didn't know what to say
• Hovercraft Full Of Eels: @EliúAbisaíDíazVásquez: "didn't like it" how? why? What specifically were they concerned about, and what metrics are we to use here to measure the quality of an attempt?
• Eliú Abisaí Díaz Vásquez: I agreed with you 100% but maybe I am guessing they asked me to solve it different because I was using split instead of iterate throught the array because in their feed back the only mentioned that I didn't solve the problem as expected, but after reading all comments I have more issues like: using StringBuffer and toString
• markspace: Probably just one of those probing interview questions. "Does the interviewee know a second way of implementing this?" Ignore the /didn't like it/ part and just focus on a different way to parse the input string.
• maaartinus: @HovercraftFullOfEels String.split is pretty crazy: github.com/google/guava/wiki/StringsExplained#splitter

Answer 3

I realize that this is old, but I just happened on it today.

Your original code does several things manually that already have built-in methods. Consider

 List<String> words = Arrays.asList(phrase.split(" "));
 Collections.reverse(words);
 return String.join(" ", words);

This creates a Collection by splitting on space and then converting that into a List. Then we can simply reverse the Collection. Finally, we join the words back together into a single string. This way, we don't iterate or join manually. We just use the built-in methods to split, reverse, and join.

Answer 4

Thanks for your fast response guys, after reading your messages I tried to solve it different:

public static void reverse(String phrase, char delimiter) {
 char[] newPhrase = new char[phrase.length()];
 int start = 0, i = 0, currentPos = newPhrase.length;
 while (i < phrase.length()) {
 if (phrase.charAt(i) == delimiter || i == phrase.length() - 1) {
 char[] word = phrase.substring(start, i).toCharArray();
 currentPos = currentPos - word.length;
 System.arraycopy(word, 0, newPhrase, currentPos, word.length);
 if (i != phrase.length() - 1) {
 newPhrase[--currentPos] = delimiter;
 }
 start = ++i;
 } else {
 i++;
 }
 }
 System.out.println(new String(newPhrase));
 }

• maaartinus: This may be faster, but it's damn hard to read. Dealing with char[]s is pretty low level and better to be avoided unless really needed. Especially in interviews.
• Rob Audenaerde: Also, if the String contains weird unicode characters, it might be the case that the character from the String does not fit in a char
• Eliú Abisaí Díaz Vásquez: @maaartinus indeed I took the main Idea from apache StringUtils.reverse