Reverse Words in a String

Medium

Yelp

3 views

Topics:

StringsTwo Pointers

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

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

1 <= s.length <= 10⁴
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Try coding it in LeetCode

Reverse Words in a String

Medium

Yelp

3 views

Topics:

StringsTwo Pointers

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

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

1 <= s.length <= 10⁴
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` contain characters other than alphanumeric characters and spaces?
What should I return if the input string `s` is null or empty?
Should I handle leading/trailing spaces and multiple spaces between words directly in the string, or am I allowed to use built-in string manipulation methods?
Is the word case-sensitive, or should I preserve the original casing of the words?
Are there any memory constraints I should be aware of if the string is very large?

Brute Force Solution

Approach

The brute force method to reverse words in a string is straightforward: split the string into individual words and then reconstruct the string by adding these words in reverse order. This guarantees we'll find the reversed string.

Here's how the algorithm would work step-by-step:

First, separate the entire string into individual words. Think of cutting the string at each space.
Next, take the last word you found.
Then, add the second-to-last word to it.
Keep adding words in reverse order until you've added the very first word.
The resulting combination of words is the reversed string.

Code Implementation

def reverse_words_brute_force(input_string):
    words = input_string.split()

    reversed_string = ""

    # Handle empty input
    if not words:
        return reversed_string

    # Start with the last word
    reversed_string = words[-1]

    #Iterate backwards and build the reversed string
    for index in range(len(words) - 2, -1, -1):

        # Add space before adding another word
        reversed_string += " " + words[index]

    return reversed_string

Big(O) Analysis

Time Complexity

O(n) – Splitting the string into words takes O(n) time, where n is the length of the string, as we iterate through the string to identify word boundaries. Reconstructing the string by appending words in reverse order also takes O(n) time because we're essentially iterating through all the words, and string concatenation is considered O(1) on average since we're concatenating references to strings and not creating copies. Therefore the overall time complexity is dominated by the string splitting and reconstruction, leading to O(n + n), which simplifies to O(n).

Space Complexity

O(N) – The described algorithm splits the input string into individual words, which requires storing these words in an auxiliary data structure, such as a list or an array. In the worst-case scenario, where the string contains N words (or the string has N characters and each character is a word), this auxiliary data structure will hold N words. Therefore, the space complexity is directly proportional to the number of words in the string, resulting in O(N) auxiliary space.

Optimal Solution

Approach

The most efficient way to reverse words in a string is to first split the string into individual words, then reverse the order of these words, and finally join them back together. We'll also handle extra spaces to ensure a clean reversed string.

Here's how the algorithm would work step-by-step:

First, separate the original string into a collection of individual words. Think of it like cutting a sentence into its building blocks.
Then, rearrange the order of these words so that the last word becomes the first, and so on.
Finally, combine these reversed words back into a single string, making sure to put a single space between each word.
Remove any extra spaces at the beginning or end of the resulting string to make it tidy.

Code Implementation

def reverse_words_in_a_string(input_string):
    words = input_string.split()

    # Filter out empty strings resulting from multiple spaces
    words = [word for word in words if word]

    # Reverse the order of the words.
    reversed_words = words[::-1]

    # Join the reversed words with a single space.
    reversed_string = ' '.join(reversed_words)

    # Remove any leading or trailing spaces.
    return reversed_string.strip()

Big(O) Analysis

Time Complexity

O(n) – Splitting the string into words takes O(n) time, where n is the length of the string. Reversing the order of the words in the collection is O(w), where w is the number of words, but since w is bounded by n (the string length), this operation is within O(n). Joining the reversed words back into a string also takes O(n) time. Removing leading/trailing spaces can be done in O(n). Therefore, the dominant factor is O(n), making the overall time complexity O(n).

Space Complexity

O(N) – The solution splits the input string into a list of individual words. In the worst-case scenario, where the input string contains only one word or all words have a single character separation, the space required to store this list will be proportional to the length of the input string, N. Therefore, the auxiliary space used is O(N) due to the storage of these words in a list. The reversed list also requires O(N) space.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty string immediately to avoid null pointer exceptions or unnecessary processing.
String with only spaces	After trimming, the string will be empty, resulting in an empty output string.
String with leading and trailing spaces	Trim the string to remove leading and trailing spaces before reversing the words.
String with multiple spaces between words	Reduce multiple spaces to single spaces during the word extraction process.
String with a single word	Return the single word after trimming any leading/trailing spaces.
Very long string	Ensure the algorithm handles large strings efficiently without excessive memory allocation by using StringBuilder or similar optimized mechanisms.
String containing non-ASCII characters	Ensure the splitting and joining logic correctly handles Unicode characters.
String contains only a single space character	The trimming process will result in an empty string, resulting in an empty string output.