Given a string s containing a set of words, transform it such that the words appear in the reverse order. Words in s are separated by one or more spaces.
Input: “I will do it.”
Output: “it. do will I”
Input: " word1 word2 " (Note: there are 3 spaces in the beginning, 2 spaces between the words and 1 space at the end.)
Output: " word2 word1 " (Note: there is 1 space in the beginning, 2 spaces between the words and 3 spaces at the end.)
Input: "word1, word2;"
Output: "word2; word1,"
Input Parameters: Function one argument, string s.
output: Return a string with the answer.
● 1 <= length of s <= 10^5
● s contains only lowercase and uppercase alphabetical characters, spaces and punctuation marks ".,?!':;-" (quotes not included).
Punctuation marks are considered a part of the word.
Usage of built-in string functions is NOT allowed.
An in-place linear solution is expected.
For languages that have immutable strings, convert the input string into a character array and work in-place on that array. Convert it back to the string before returning. Ignore the extra linear space used in that conversion, as long as you're only using constant space after conversion to character array.
Trivia: This is a very old interview question. Google used it as one of their qualifier questions in Google CodeJam in the past, too.
One idea for the solution is:
1) Reverse the whole string.
2) Then reverse the individual words.
For example, if the input is:
s = "Have a nice day!"
1) Then first reverse the whole string,
s = "!yad ecin a evaH"
2) Then reverse the individual words,
s = "day! nice a Have"
The first pass over the string is obviously O(n/2) = O(n). The second pass is O(n + combined length of all words / 2) = O(n + n/2) = O(n), which makes this an O(n) algorithm.