Reverse all the words in a given string

Question

I have read this and I want to know how the solution that I came up with in my interview compares with the top solution.

public static String reverseWords(String s) {
    if (s == null) return null;
    else if (s.equals("")) return "";
    else {
        s = s.trim();
        int index;
        for (index = 0; index < s.length(); index++) {
            if (s.charAt(index) == ' ') break;
        }
     String res = reverseWords(s.substring(index)) + " " + s.substring(0, index);
        return res.trim();
    }
}

My code is more space inefficient, as I was concatenating instead of appending, so I created many copies of new strings. What about time complexity though? They both seem to be in \$O(n)\$ time, but I'm not sure about the constant factors.

Also, how does split() specifically perform against charAt()? I knew about the split() operation, but I opted for charAt() because I thought that split() was more expensive (wasn't sure; but I think it does some regex processing, which may be expensive). Should I have opted for split() instead?

Answer 1

Your solution is simple enough.

If you want to use this approach, you could tighten up the implementation a bit, mainly using String.indexOf() and eliminating the "" special case:

public static String reverseWords(String s) {
    if (s == null) return s;
    int space = s.indexOf(' ');
    if (space < 0) {
        return s;
    } else {
        return reverseWords(s.substring(space + 1)) + " " + s.substring(0, space);
    }
}

As you feared, though, it's not a performant solution. For every word in the input, you end up taking two substrings and perform two string concatenations. Doing String.split() as @janos suggested would scale better, since…

• it requires fewer substring allocations
• it requires fewer string concatenations
• there is less function call overhead
• there is no danger of stack overflow

If you present your solution in an interview situation, be sure to mention the caveat that the recursion doesn't scale well, and be prepared to follow up with an alternate solution if your interviewer requests it.

Answer 2

Some comments.

• It is safer to swap the order when compare - even if you have already checked for null:

else if ("".equals(s)) return "";

Even better 1-liner:

if (s == null || "".equals(s)) return s;

• What if you have other separators then space - like tabs, new-lines, \r etc?

if (s.charAt(index) == ' ')

Use regex to match all white-spaces:

// global
Pattern p = Pattern.compile("\\s+");

Actually - just think about it - your solution is not working for such cases, maybe regex is not the best way either.

Regarding your questions: split() is slower then charAt() because former is kind of a regex search in string, charAt is just similar to index access to array.

My opinion is that this "mambo-jumbo" with searching spaces and revering the rest of the string recursively is not worth any theoretical gains it possibly has. Code is difficult to understand - it took me a minute to get the idea what you are doing here.

Why not just to split for all spaces and reverse iterate over tokens? This solution does not preserve spaces BTW, so maybe not good. So question you should ask on interview - if spaces needs to be preserved on not.

I didn't read your link BTW - this maybe exactly what is proposed there - because the point is to comment on your code and not to compare with somebody else.