Code Implementation

class Solution:
    def reverseWords(self, s: str) -> str:
        # Split the string into words, removing extra spaces
        words = s.strip().split()
        # Reverse the list of words
        words.reverse()
        # Join the words with a single space
        return ' '.join(words)
      

class Solution {
public:
    string reverseWords(string s) {
        istringstream iss(s);
        vector<string> words;
        string word;
        while (iss >> word) {
            words.push_back(word);
        }
        reverse(words.begin(), words.end());
        string result;
        for (int i = 0; i < words.size(); ++i) {
            if (i > 0) result += " ";
            result += words[i];
        }
        return result;
    }
};
      

class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        StringBuilder sb = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            sb.append(words[i]);
            if (i != 0) sb.append(" ");
        }
        return sb.toString();
    }
}
      

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.trim().split(/\s+/).reverse().join(' ');
};
      

Problem Description

You are given a string s that may contain leading, trailing, or multiple spaces between words. Your task is to reverse the order of the words in s. A word is defined as a sequence of non-space characters. The returned string should have words separated by a single space, and there should be no leading or trailing spaces.

• Each word in the output should appear in reverse order compared to the input.
• Multiple spaces between words in the input should be reduced to a single space in the output.
• There is exactly one valid answer for each input.

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

Thought Process

The core of this problem is to reverse the order of words in a string, while also cleaning up any extra spaces. Initially, you might think about reversing the characters of the entire string and then reversing each word, but this can get tricky with the spaces.

Instead, a simpler approach is to:

• Extract all the words from the string, ignoring extra spaces.
• Reverse the order of these words.
• Join them back together with a single space.

The brute-force method would involve manually parsing the string character by character, handling spaces, and building the result, but using language features like split() and join() makes the solution much cleaner and less error-prone.

Solution Approach

Here’s a step-by-step breakdown of the efficient approach:

1. Trim the input string: Remove leading and trailing spaces so that extra spaces at the ends do not affect the result.
2. Split the string into words: Use a split function (with regular expressions or default whitespace splitting) to break the string into a list/array of words. This automatically collapses multiple spaces between words.
3. Reverse the list of words: Use a built-in reverse function or reverse loop to change the order of the words.
4. Join the words back into a string: Use the join function to concatenate the words with a single space between each.

Why this design?

• Splitting handles all whitespace issues for us, so we don’t need to parse character-by-character.
• Reversing a list or array is a common operation and is efficient.
• Joining ensures there is exactly one space between each word and no extra spaces at the ends.

Example Walkthrough

Input: s = " hello world! "

1. Trim the string: Result is "hello world!"
2. Split into words: The split operation produces ["hello", "world!"]
3. Reverse the list: Now we have ["world!", "hello"]
4. Join with spaces: The final result is "world! hello"

Notice how all extra spaces are removed and the words are in the correct reversed order.

Time and Space Complexity

• Brute-force approach: If you manually parse the string character by character, handling spaces and reversing individual words, the time complexity is O(n), but the code is more complex and error-prone.
• Optimized approach (using split, reverse, join): Each step (splitting, reversing, joining) is O(n), where n is the length of the input string. The space complexity is also O(n), as we store the list of words and the final result.
• Why O(n)? Because every character in the string is visited a constant number of times by the various operations.

Summary

The key to solving "Reverse Words in a String" efficiently is to leverage built-in string and array methods to handle splitting, reversing, and joining. This approach avoids manual parsing and makes the code concise and readable. By focusing on extracting words and then reversing their order, we ensure that all spacing issues are handled automatically, resulting in a clean and elegant solution.