Reverse Words in a String

mediumFREEStrings & ParsingApple DSA

Given a string s, reverse the order of words. A word is a sequence of non-space characters. Remove leading/trailing spaces and reduce multiple spaces to a single space.

Example

Input

the sky is blue

Output

blue is sky the

Reasoning

The input string the sky is blue is split into individual words: the, sky, is, blue
These words are then reversed in order to produce the desired output
The reversed words are joined back together with a single space in between each word: blue is sky the
The resulting string has no leading or trailing spaces and only single spaces between words, yielding the final output: blue is sky the

Constraints

1 <= len(s) <= 10^4
s contains English letters, digits, and spaces

More from Apple DSA

Happy Numbereasy Longest Consecutive Sequencemedium Single Numbereasy Path Sumeasy Invert Binary Treeeasy

Concept primer

Background Knowledge

The problem "Reverse Words in a String" involves manipulating a string by reversing the order of its constituent words. To tackle this, it's essential to understand the basics of string processing and how to work with words within a string. A word is defined as a sequence of non-space characters. This means that any character that is not a space (such as letters, digits, or punctuation) can be part of a word.

In the context of this problem, it's also crucial to grasp the concept of tokenization, which is the process of breaking a string into individual words or tokens. Tokenization often involves identifying and separating words based on spaces or other delimiters. Additionally, understanding how to handle edge cases such as leading, trailing, or multiple spaces is vital. This includes recognizing how to remove or reduce these spaces to ensure the output string is clean and formatted as required.

The problem requires a combination of string manipulation techniques, including splitting, reversing, and joining strings. Familiarity with these operations and how they can be applied to achieve the desired outcome is key. Furthermore, considering the efficiency of the solution in terms of time and space complexity is important, especially for larger input strings.

Algorithm/Approach

The general approach to solving this type of problem involves a combination of string manipulation and iteration. A common algorithm pattern is to first preprocess the input string to remove leading and trailing spaces and reduce multiple spaces to a single space. Then, the string can be split into individual words, which are stored in a data structure such as an array or list. The next step typically involves reversing the order of the words in the data structure. Finally, the reversed words are joined back together into a single string with spaces in between, resulting in the final output.

Step-by-Step Strategy

To implement the solution:

Remove leading and trailing spaces from the input string s.
Replace multiple spaces with a single space to normalize the string.
Split the normalized string into an array of words.
Reverse the order of the words in the array.
Join the reversed words back into a string with a single space between each word.

Common Pitfalls

Failing to handle edge cases such as empty strings, strings with only spaces, or strings with leading/trailing spaces.
Not correctly reducing multiple spaces to a single space, which can affect the splitting of words.
Incorrectly reversing the order of words, such as reversing the characters within each word instead of reversing the order of the words themselves.

Time & Space Complexity

The expected time complexity for this problem is $O(n)$ , where $n$ is the length of the input string s, because each character in the string is processed at least once. The space complexity is also $O(n)$ , as in the worst case, the output string could be of the same length as the input string, and additional space is needed to store the array of words.

solution.py

Python 3.13

Test results