Reverse Words in Java

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 formatting. 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 space as the delimiter.
Reverse the order of the words.
Join the reversed words back into a single string with a space separator.

Let's discuss a naive solution and then move on to an optimized solution.

Naive Solution

A naive approach would be to manually iterate through the string, identify words, and then reverse their order. This approach is not optimal due to its complexity and potential for errors.

Optimized Solution

An optimized solution leverages built-in string manipulation functions 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 divide the input string into an array of words.
Reverse the array of words.
Use the join() method to concatenate the reversed words into a single string with spaces.

Code Implementation

public class ReverseWords {
    public static String reverseWords(String s) {
        // Split the input string by spaces to get the words
        String[] words = s.split(" ");
        
        // Use a StringBuilder to efficiently build the reversed string
        StringBuilder reversed = new StringBuilder();
        
        // Iterate over the words array in reverse order
        for (int i = words.length - 1; i >= 0; i--) {
            reversed.append(words[i]);
            if (i != 0) {
                reversed.append(" ");
            }
        }
        
        // Convert the StringBuilder to a String and return
        return reversed.toString();
    }

    public static void main(String[] args) {
        String input = "sky is blue";
        String output = reverseWords(input);
        System.out.println(output);  // 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 we are splitting the string into words and then iterating over the words array. The space complexity is also O(n) due to the storage required for the words array and the StringBuilder.

Edge Cases

Consider the following edge cases:

Input string with multiple spaces between words: " sky is blue "
Input string with leading or trailing spaces: " sky is blue "
Input string with a single word: "sky"
Empty input string: ""

Our algorithm handles these cases effectively by using the split() method, which ignores leading and trailing spaces and treats multiple spaces as a single delimiter.

Testing

To test the solution comprehensively, consider the following test cases:


public static void main(String[] args) {
    // Test case 1: Normal case
    System.out.println(reverseWords("sky is blue").equals("blue is sky"));
    
    // Test case 2: Multiple spaces
    System.out.println(reverseWords("  sky  is  blue  ").equals("blue is sky"));
    
    // Test case 3: Leading and trailing spaces
    System.out.println(reverseWords("  sky is blue  ").equals("blue is sky"));
    
    // Test case 4: Single word
    System.out.println(reverseWords("sky").equals("sky"));
    
    // Test case 5: Empty string
    System.out.println(reverseWords("").equals(""));
}

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 words in a string using an efficient algorithm in Java. 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:

Reverse Words in a String - Java Solution with O(n) Time Complexity