Once again Ruby is really nice, it's super short and you can just write the steps from left to right. Split the string into words, reverse each word, then join them back together.
def reverse_words(s) s.split.map(&:reverse).join(" ") end
Here I first reverse the order of the words and then reverse the entire string.
def reverseWords(self, s): return ' '.join(s.split()[::-1])[::-1]
That's a bit shorter than the more obvious one:
def reverseWords(self, s): return ' '.join(x[::-1] for x in s.split())
That double reversal in Ruby:
def reverse_words(s) s.split.reverse.join(" ").reverse end
The double reversal is not just shorter but also faster. Trying both versions as well as the optimized obvious solution (using a list comprehension instead of a generator expression), five attempts each:
>>> from timeit import timeit >>> setup = 's = "Let\'s take LeetCode contest"' >>> statements = ("' '.join(s.split()[::-1])[::-1]", "' '.join(x[::-1] for x in s.split())", "' '.join([x[::-1] for x in s.split()])") >>> for stmt in statements: print ' '.join('%.2f' % timeit(stmt, setup) for _ in range(5)), 'seconds for:', stmt 0.79 0.78 0.80 0.82 0.79 seconds for: ' '.join(s.split()[::-1])[::-1] 2.10 2.14 2.08 2.06 2.13 seconds for: ' '.join(x[::-1] for x in s.split()) 1.27 1.26 1.28 1.28 1.26 seconds for: ' '.join([x[::-1] for x in s.split()])
With many more words, the double reversal's advantage gets even bigger:
>>> setup = 's = "Let\'s take LeetCode contest" * 1000' >>> for stmt in statements: print ' '.join('%.2f' % timeit(stmt, setup, number=1000) for _ in range(5)), 'seconds for:', stmt 0.16 0.14 0.13 0.14 0.14 seconds for: ' '.join(s.split()[::-1])[::-1] 0.69 0.71 0.69 0.70 0.70 seconds for: ' '.join(x[::-1] for x in s.split()) 0.63 0.68 0.63 0.64 0.64 seconds for: ' '.join([x[::-1] for x in s.split()])
I didn't use
split, as I thought it may contain multiple consecutive white spaces. It turns out that I was over-thinking.
But why double reversal is much faster than reversing each word separately, and why the list comprehension version is faster than the generator expression version?
@NoAnyLove I think double reversal is faster because it's pretty much all C code from the library, there's almost no Python code from us to run. One reason list comprehension is faster than generator expression is that
join creates a list from the generator, so it's faster to build one directly. Also, a generator is probably slower due to its more general nature. Both generator and comprehension produce values, but the comprehension just directly stores the values while the generator yields them and this yielding is more overhead. At least that's what I think.
Hi @StefanPochmann, thanks for you explanation
@StefanPochmann Sorry this is off topic but I just need to know and I can't DM you. How did you get so good at this? All your code is all over the place and is amazing and concise. Were you always this good or was it just a ton of practice? Can you really knock out a majority of these questions in 30 minutes with the solutions you come up with?
@alkaar Yes, practice. I don't have statistics but I believe I solve the majority in well under 30 minutes, though not necessarily with the solutions I post. I do spend some extra time to rethink stuff and polish the solutions I post. That can vary a lot. For this particular problem, I maybe took less than one minute to read the problem and write the obvious
return ' '.join(x[::-1] for x in s.split()) solution. I think I came up with
' '.join(s.split()[::-1])[::-1] only a few days later, but of course I wasn't thinking about this the whole time :-)
I really enjoyed the second Python solution. Thank you!
@StefanPochmann Not sure what I missed but why is a setup string 1000 times longer, executed 1000 times taking less time than the short string executed once??
@s I think you're overlooking the default
@StefanPochmann Oh right!! Thank you sir!
Thank you! There is a analysis into this question : http://liqichen.com/daily-leetcode557-reverse-words-in-a-string-iii/
@AlexS6688 Do you realize that you made it much worse?
@StefanPochmann I think it is more readable.... just depends on how you judge a code
@AlexS6688 I think both are about equally readable, but yours is more code, more complicated (adding and removing a space at the end), less pythonic, and very inefficient (only O(n2) instead of O(n)).
@StefanPochmann Whatever :) I like my code
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.