algoadvance

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.

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.

Clarifying Questions

1. Should leading or trailing spaces be removed?
   • Yes, they should be removed in the output.
2. How should multiple spaces between words be handled?
   • They should be reduced to a single space.
3. What about empty strings or strings with only spaces?
   • They should return an empty string.

Strategy

1. Strip the string: Remove any leading or trailing whitespace.
2. Split the string by spaces: This will give us a list of words. Python’s split() method will handle multiple spaces by default.
3. Reverse the list of words.
4. Join the reversed list with a single space.
5. Return the result.

Code

def reverseWords(s: str) -> str:
    # Step 1: Strip the string to remove any leading or trailing spaces
    trimmed = s.strip()
    
    # Step 2: Split the string by spaces, which will also handle multiple spaces
    words = trimmed.split()
    
    # Step 3: Reverse the list of words
    words.reverse()
    
    # Step 4: Join the reversed list with a single space
    result = ' '.join(words)
    
    return result

# Test cases
print(reverseWords("the sky is blue"))  # Output: "blue is sky the"
print(reverseWords("  hello world  "))  # Output: "world hello"
print(reverseWords("a good   example"))  # Output: "example good a"
print(reverseWords("    "))  # Output: ""
print(reverseWords(""))  # Output: ""

Time Complexity

• Stripping and Splitting: Both operations are O(n), where n is the length of the string.
• Reversing the List: O(k), where k is the number of words (in the worst case, k can be at most n if every character is a single word followed by a space).
• Joining the List: O(n).

Overall, the time complexity for this approach is O(n).

Summary

This solution efficiently reverses the words in a string by leveraging Python’s built-in string handling capabilities. It ensures correct handling of leading/trailing spaces and multiple spaces between words, providing a clean and effective solution.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?