Naive Solution

The most straightforward approach is to split the string by spaces, filter out empty strings, reverse the resulting list of words, and then join them back together with single spaces.

def reverse_words_naive(s):
    words = s.split()
    words = [word for word in words if word]
    words.reverse()
    return " ".join(words)

Big(O) Runtime: O(n), where n is the length of the string s. This is because split() takes O(n), filtering takes O(n), reverse() takes O(n), and join() takes O(n).

Big(O) Space: O(n), because we create a list of words which can be as large as the original string.

Optimal Solution

This approach aims to reduce space complexity. It involves trimming leading/trailing spaces, iterating the string in reverse to identify words, and building the reversed string incrementally.

def reverse_words_optimal(s):
    s = s.strip()
    n = len(s)
    result = ""
    i = n - 1
    while i >= 0:
        if s[i] == ' ':
            i -= 1
            continue
        j = i
        while j >= 0 and s[j] != ' ':
            j -= 1
        word = s[j+1:i+1]
        if result == "":
            result = word
        else:
            result += " " + word
        i = j
    return result

Big(O) Runtime: O(n), where n is the length of the string s. We iterate through the string once.

Big(O) Space: O(k), where k is the length of reversed string. If we consider the output to be part of space complexity, it will be O(n).

Edge Cases

• Leading/Trailing Spaces: The strip() method handles these.
• Multiple Spaces Between Words: The optimal solution skips extra spaces and only appends a single space between words.
• Empty String: Returns an empty string (handled by the strip() method in optimal solution).
• String with Only Spaces: strip() will result in an empty string, and the loops won't execute, returning an empty string.

Follow-up: In-Place Reversal

In-place reversal is more complex and typically involves converting the string to a list of characters (if the string is immutable) and then using pointer manipulations to reverse the whole string, then reverse each word. Python strings are immutable, so achieving a true O(1) extra space solution is not directly possible without using list and libraries that allows O(1) space complexity.