Solution critique: reversing words in a sentence

Question

I had a technical interview and was given the following question:

Write a function that takes a sentence and returns the sentence with the words in reverse order (i.e. "hello world" becomes "world hello").

Here is the solution that I gave in Java:

/** Takes a sentence as an input and returns the sentence with the words in
 *  reversed order. */
private static String reverseSentence(String sentence) {
    String[] words = sentence.split("\\s+");
    String reversedString = "";
    for (int k = words.length - 1; k >= 0; k -= 1) {
        reversedString += " " + words[k];
    }
    return reversedString.substring(1);
}

I got to thinking that there has to be a more efficient way to solve this problem than this. I don't see this being asked in a technical interview for a top company if this solution turns out to be the best one and there isn't one more efficient/elegant.

Can anyone think of a better way to do this?

Ya.. Use a `StringBuilder` instead of `String reversedString`. String concatenation (especially within a loop) isn't efficient. — TheLostMind, Nov 24 '14 at 09:54
There is a `Collections.reverse` method: http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#reverse(java.util.List) you can probably make use of it. — SirDarius, Nov 24 '14 at 09:57
what if helloworld? What if my string contains just a space? Although i wasn't the interviewer there but they certainly look for exception/edge case handling. — SMA, Nov 24 '14 at 09:57
@almasshaikh `\s` matches any whitespace character: `[ \t\n\x0B\f\r]` — SirDarius, Nov 24 '14 at 09:59
@almasshaikh good point, then the string needs to be split at word limits. — SirDarius, Nov 24 '14 at 10:01
Always ask about the use case before delving in with an answer. There's often a trade-off between speed and maintainability. — Bathsheba, Nov 24 '14 at 10:02
@SirDarius - What almas is trying to say is - "irrespective of the number of spaces present, the OP is always adding only one space.." :) — TheLostMind, Nov 24 '14 at 10:02
@SirDarius Yes that's the way but before running the horses, i always tend to ask the question to interviewer like is it really going to be a space seperated string? — SMA, Nov 24 '14 at 10:03
If you improve your solution to use `StringBuilder` and preserve whitespaces, make sure to initialize the `StringBuilder` with an initial capacity of `sentence.length()`. That way you avoid resizing of the internal buffer (which is amortized constant time, but still needless since you know the exact length of the result). — misberner, Nov 24 '14 at 10:05

score 1 · Answer 1 · edited May 23 '17 at 12:12

1

Here are better ways to concatenate the elements of the sentence: What's the most elegant way to concatenate a list of values with delimiter in Java?

Also, sentence.split("\\s+") only works when the input is clean (people do make typos). There is also the questions what should happen to punctuation. World! Hello, does look very odd.

edited May 23 '17 at 12:12

Community

1
1

answered Nov 24 '14 at 10:02

Aaron Digulla

321,842
108
597
820

`String.join` is a good choice, too. Even if it might not be quite as efficient, it's "out of the box". – laune Nov 24 '14 at 11:32

score 0 · Answer 2 · edited May 23 '17 at 12:12

Except the comment, to use a more efficient data structure (StringBuilder) to create the string, I don't think there is much you can do. The time complexity to reverse an array is n/2 (How do I reverse an int array in Java?) but afterwards you would still need to concatenate all of the items, which should be n - since you're concatenating them right away you get down from 3n/2 to only n.

laune · Answer 3 · 2014-11-24T10:34:34.297

Once you have reversed the array by swapping references (0 with length-1, etc) you can

String reversedSentence = String.join( " ", words );

But I think it is better to avoid a String array.

String s = "the quick brown fox";
StringBuilder sb = new StringBuilder();
int p = s.length();
int np = -1;
while( (np = s.lastIndexOf( " ", p-1 )) != -1 ){
    sb.append( s.substring( np + 1, p ) ).append( " " );
    p = np; 
}
sb.append( s.substring( 0, p ) );
System.out.println( sb.toString() );

This assumes that the input string is properly "normalized".

score 0 · Answer 4 · answered Nov 24 '14 at 11:23

Sometimes this question is asked with a constraint asking for it to be done without using any extra memory.

One answer to this modified question is:

First reverse each word in the sentence ("Hello World" -> "olleH dlroW")
Then reverse the entire sentence ("olleH dlroW" -> "World Hello")

Solution critique: reversing words in a sentence

4 Answers4