5
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Hi! Welcome to Code Review. Half of your question is on-topic, as it asks for a Code Review. Half is not, as it asks for an explanation of someone else's code. I will Vote To Close this question until it is removed. \$\endgroup\$ – TheCoffeeCup Oct 25 '15 at 18:53
  • \$\begingroup\$ @MannyMeng So where should I ask this question then? StackOverflow? \$\endgroup\$ – fluffychaos Oct 25 '15 at 19:21
  • \$\begingroup\$ Just remove the part asking about the comparison, as it is not your code, and you will be fine. Currently, there is no place to ask for code explanations. \$\endgroup\$ – TheCoffeeCup Oct 25 '15 at 19:26
  • \$\begingroup\$ @MannyMeng Done \$\endgroup\$ – fluffychaos Oct 25 '15 at 20:21
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for listing the reasons for using String.split() clearly! \$\endgroup\$ – fluffychaos Oct 27 '15 at 1:13
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you! I forgot to mention that the interviewer wanted multiple white spaces to be one white space. I.e. "this is an example" should be "example an is this" \$\endgroup\$ – fluffychaos Oct 27 '15 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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