How to Solve Reverse Words in a String

Given an input string s, reverse the order of the words without reversing the words themselves.

Note that the input string s may contain multiple spaces between any given two words, as well as leading or trailing spaces; however, the return sentence should only have a single space between all words and should not have any leading or trailing space.

Example 1 Input: s = “This sentence is forwards” Output: “forwards is sentence This”

Input: s = “ a blue whale rhino Boston arepa heaven “ Output: s = “heaven arepa Boston rhino whale blue a“

Constraints

• The string will only contain upper-case and lower-case letters (no punctuation)
• 1 <= s.length <= 10,000

There are two methods for reversing words in a string. One method is splitting on spaces, reversing the list and joining. Alternatively, you can reverse the string in place.

Approach 1: Split on Spaces, Reverse the List and Join

This specific problem can be tackled in a manner similar to how we'd approach it if we were solving manually (remember, in an interview setting you always want to communicate your strategy, especially for multi-step solutions like this):

Identify all the individual words at the beginning and end of the string, and then trim/eliminate the unneeded space. Reverse the order of the words and build the string back up to form the result.

Diving into the code, most modern programming languages provide a standard library method to split a string on a given character, in this case ” “.

Reverse Words in a String Python and Ruby Solutions - Split on Spaces, Reverse the List and Join

When we use this method, note how both trailing and leading spaces end up in the words list as empty strings. We can then filter the words list in order to remove the empty strings:

All we have left to do now is reverse the list and join the words with a space between them, and in the end we have a fairly straightforward algorithm.

Time/Space Complexity

• Time complexity: O(n), as the interpreter iterates over the input string once and the list of words twice.
• Space complexity: O(n), to store the list of words after splitting by spaces.

Approach 2: In-place

Let’s pretend that you find yourself in an interview and your interviewer has asked a follow up question: “Is it possible to solve this problem and be more efficient from a space complexity standpoint?”

We already know our first solution is O(n), leaving O(log(n)) and O(1) as the two most common ways to improve. A log(n) algorithm is most often related to dividing and conquering or binary search, and neither of those concepts apply here. So how can we make our solution constant space? We aren’t allowed extra memory, so the only way to do so is by mutating the string in place.

Depending on the coding language being used, strings are either mutable or immutable. If a given language has immutable strings this means that the string can't be edited in-place without creating a new string in memory (which is a O(n) operation, with n being the length of the string). Conversely, if a given language has mutable strings that means the string can be edited in-place, similar to an array/list.

For example, in Ruby:

To read more about mutable vs immutable strings, check out this article on the topic by MIT.

If coding in a language with immutable strings (Python, Javascript, Java, etc.) mutating the string will not work, however there may be classes or libraries (such as Stringbuilder in Java) that would allow you to employ a similar approach - an interviewer may let you just assume you have one of these imported.

To mutate the string in place the algorithm can again be broken down into multiple steps:

1. Identify the distinct words by iterating over the string looking for spaces
2. Reverse the words in place one word at a time, trimming/skipping extra spaces while iterating
3. Trim any unneeded space from the end of the string

Reverse Words in a String Ruby Solution - In-place String Mutation

Time/Space Complexity

• Time complexity: O(n), as we iterate over the string with multiple pointers but only do one iteration of each pointer.
• Space complexity: O(1)

How do you reverse each word in a string?

There are two approaches you can take. The first is to split the string on spaces, reverse each word individually (see our in-depth solution to “reverse a string”), and then join them back. This approach runs in O(n) time and requires O(n) space.

A more space-efficient solution is to reverse the entire sentence in place. Note that this approach only works in languages where strings are mutable. To mutate the string in place, you would identify words by iterating over the string looking for spaces. Then you’d reverse the words in place one word at a time. Finally you’d trim any unneeded spaces from the end of the string.

This solution still runs in linear time but requires only constant space.

Why can’t I just use the reverse() function to solve this problem?

You can… if you’re implementing sentence reversal in the real world. In an interview, however, you need to show your interviewer that you know how built-in functions work under the hood – that’s part of why interviewers ask questions like this.

How do you reverse each word in a string in Python?

Because strings are immutable in Python, you wouldn’t be able to reverse the string in place. As such, you can use the approach where you split the string on spaces, reverse each word, and then join them back, like so:

def reverseWords(self, s: str) -> str:
3        words = s.split(' ')
4        filtered_words = [s for s in words if s != '']
5        return ' '.join(filtered_words[::-1])