LeetCode #151 Reverse Words in a String

Medium

Problem

Given an input string, reverse the string word by word.

Example:

Input: "the sky is blue",
Output: "blue is sky the".

Note:

• A word is defined as a sequence of non-space characters.
• Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
• You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up: For C programmers, try to solve it in-place in O(1) space.

Solution

Split string into words and swap words from start and end until meet mid item.

Complexity

Splitting this string takes O(n) time which n denotes to string length. And swapping to the middle word uses O(n/2) time. Hence total time complexity is O(n + n/2) = O(n).

It needs a new list for saving each words which will allocate O(n) extra space.