Reversing a Sentence

would recommend the Plate of Polish Specialties - a little of everything
Karczma, Brooklyn, NYC

Here was a problem that I found intriguing - not the first part , but the second part that challenges us to reverse a string in place.

Given a string of words delimited by spaces, reverse the words in string. For example, given "hello world here", return "here world hello"

Follow-up: given a mutable string representation, can you perform this operation in-place?

Solving the first part

.. is straight forward

  • use a library to split the sentence
  • reverse the resultant array or list
  • convert the array back to a string

While the solution is easy and makes use of a library, it does use up memory and may not be applicable for larger use cases.

Operation in Place

My initial approach started off right, by traversing the sentence from opposite ends towards the center, and then swapping words as white spaces were encountered. The problem is that all words have different sizes and may not fit into the space created by the swap

A better approach is to reverse all the characters (rather than each individual word) during the first pass

We can now traverse the string a second time and reverse each word encountered prior to the white space