Reverse Words in a String - Time Complexity: O(n) - Python

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 one space for simplicity.

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

Example:

Input:  input = "sky is blue"

Output:  "blue is sky"

Understanding the Problem

The core challenge of this problem is to reverse the order of words in a given string. This is a common problem in text processing and has applications in various fields such as natural language processing and data cleaning. A potential pitfall is to mistakenly reverse the characters within the words instead of reversing the order of the words themselves.

Approach

To solve this problem, we can follow these steps:

Split the input string into words using spaces as delimiters.
Reverse the list of words.
Join the reversed list of words back into a single string with spaces in between.

Let's discuss a naive solution and then an optimized solution:

Naive Solution

The naive solution involves manually iterating through the string to identify words and then reversing their order. This approach is not optimal due to its complexity and potential for errors.

Optimized Solution

The optimized solution leverages Python's built-in string and list methods to achieve the desired result efficiently. This approach is both simple and effective.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

Use the split() method to split the input string into a list of words.
Reverse the list of words using slicing or the reverse() method.
Use the join() method to concatenate the reversed list of words into a single string with spaces in between.

Code Implementation

def reverse_words(s: str) -> str:
    # Split the input string into words
    words = s.split()
    # Reverse the list of words
    words.reverse()
    # Join the reversed list of words into a single string
    reversed_string = ' '.join(words)
    return reversed_string

# Example usage
input_string = "sky is blue"
output_string = reverse_words(input_string)
print(output_string)  # Output: "blue is sky"

Complexity Analysis

The time complexity of this solution is O(n), where n is the length of the input string. This is because splitting the string, reversing the list, and joining the list all take linear time. The space complexity is also O(n) due to the storage required for the list of words.

Edge Cases

Consider the following edge cases:

Empty string: The output should also be an empty string.
String with multiple spaces: The solution should handle multiple spaces correctly by splitting and joining words appropriately.

Examples:

assert reverse_words("") == ""
assert reverse_words("   ") == ""
assert reverse_words("hello   world") == "world hello"

Testing

To test the solution comprehensively, consider a variety of test cases:

Simple cases with a few words.
Edge cases with empty strings and multiple spaces.
Long strings to test performance.

Example test cases:

def test_reverse_words():
    assert reverse_words("sky is blue") == "blue is sky"
    assert reverse_words("") == ""
    assert reverse_words("   ") == ""
    assert reverse_words("hello   world") == "world hello"
    assert reverse_words("a b c d e") == "e d c b a"
    print("All test cases pass")

test_reverse_words()

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable parts.
Leverage built-in functions and libraries to simplify your solution.
Think about edge cases and how your solution handles them.
Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to reverse the order of words in a string using an efficient algorithm. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving your coding skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: