See the original problem on HackerRank.
Solutions
A simple solution that makes use of extra space consists in simply copying words backwards to a temporary array starting from the last one.
However, an classical inplace solution exists and works in two steps: first reverse the string blindly and then reverse every single word individually.
Note that the input of this puzzle contains multiple lines and empty ones must be preserved.
Here is a C++ solution:


To be super strict, the lambda should be rewritten this way:


Since isalnum
returns nonzero value if the character is an alphanumeric character, 0 otherwise. Also, to use this function safely, the argument should first be converted to unsigned char
.
This is linear in time and constant in space (assuming s
is constant).
A possible open question is: how can you solve this problem when the input does not fit the main memory?
Patterns
The solution above can be rewritten in terms of a few functional patterns.
The idea is still to first reverse the string blindly, then to “group” letters together to form words we can use a pattern that in C++ is called chunk_by
that simply groups together all contiguous elements of a range satisfying a certain condition. The condition here is something like “same category of letter” that is either a special character or an alphanumeric character.
Here is a nextgeneration C++ solution making use of ranges:


Then printing output
gives the desired result. This solution works lazily.
A variation of this solution that changes inplace on the input string can be found here below:


The complete discussions about these patterns for C++ aficionados can be found here.
Another slick solution in Python by umuril_lyerood:


Here is a functional one in Javascript by Francesco Osti and Simone Busoli:

