Solution 1 (using built-in functions):

This problem can also be solved with the help of built-in functions, such as strip(), split(), and join().

def reverse_words(s: str) -> str:
    # Trim leading and trailing spaces
    s = s.strip()

    # Split the string into a list of words
    words = s.split()

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

    # Join the reversed words to form the final string
    result = ' '.join(reversed_words)

    return result

Solution 2 (without built-in functions):

Here’s a Python implementation for the reverse_words function without using built-in functions:

def reverse_words(s: str) -> str:
    def reverse_string(start, end):
        # Helper function to reverse characters in-place
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

    # Step 1: Convert string to a list of characters for in-place manipulation
    s = list(s)

    # Step 2: Reverse the entire string
    reverse_string(0, len(s) - 1)

    # Step 3: Reverse each word individually
    start = 0
    for end in range(len(s)):
        if s[end] == ' ':
            reverse_string(start, end - 1)
            start = end + 1

    # Reverse the last word
    reverse_string(start, len(s) - 1)

    # Step 4: Convert the list back to a string
    result = ""
    for word in s:
      result = result + word

    return result

# Example usage:
print(f"'{reverse_words('Hello World')}'") #Output: 'World Hello'
print(f"'{reverse_words('Coding Interview Practice')}'") 
  #Output: 'Practice Interview Coding'
print(f"'{reverse_words('Python is fun')}'") #Output: 'fun is Python'

Explanation:

  • We create a helper function reverse_string to reverse a portion of the string in-place.
  • We convert the input string into a list of characters for in-place manipulation.
  • We first reverse the entire string.
  • Then, we iterate through the string, identifying words by spaces and reversing each word individually.
  • Finally, we convert the list back to a string.

Time Complexity:

The time complexity is O(n), where n is the length of the input string. We perform a constant amount of work for each character in the string. Let’s break down the time complexity of the provided solution step by step:

  1. Converting string to a list of characters:
    • This step takes O(n) time, where n is the length of the input string. Converting a string to a list of characters involves iterating through each character in the string.
  2. Reversing the entire string:
    • The reverse_string helper function is used to reverse the entire string in-place. It has a time complexity of O(n/2), which simplifies to O(n) because we consider only the dominant term.
  3. Reversing each word individually:
    • We iterate through each character in the list once, and for each word (separated by spaces), we apply the reverse_string function. The total time complexity for this step is O(n).
  4. Converting the list back to a string:
    • This step also takes O(n) time since we iterate through each character in the list to join them back into a string.

Overall, the dominant factor contributing to the time complexity is the linear traversal of the input string and characters. The time complexity of the entire solution is O(n), where n is the length of the input string. This makes the solution efficient and linear with respect to the input size.

Space Complexity:

  • The space complexity is O(1) since the solution manipulates the characters in-place and does not use additional data structures that scale with the size of the input.