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 while maintaining the integrity of each word. This problem is significant in text processing and has applications in natural language processing, data formatting, and more. A common pitfall is to reverse the characters of the string instead of the words.

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 spaces in between.

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

Naive Solution

The naive solution involves splitting the string into words, reversing the list of words, and then joining them back together. This approach is straightforward but not the most efficient in terms of space complexity.

Optimized Solution

An optimized solution can be achieved by using a two-pointer technique to reverse the words in place, which can be more space-efficient.

Algorithm

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

Convert the input string to a character array for in-place manipulation.
Reverse the entire character array.
Iterate through the reversed array and reverse each word individually.
Convert the character array back to a string and return it.

Code Implementation

public class ReverseWords {
    public static String reverseWords(String s) {
        // Convert the string to a character array
        char[] str = s.toCharArray();
        
        // Reverse the entire string
        reverse(str, 0, str.length - 1);
        
        // Reverse each word in the reversed string
        int start = 0;
        for (int end = 0; end < str.length; end++) {
            if (str[end] == ' ') {
                reverse(str, start, end - 1);
                start = end + 1;
            }
        }
        // Reverse the last word
        reverse(str, start, str.length - 1);
        
        // Convert the character array back to a string
        return new String(str);
    }
    
    // Helper method to reverse a portion of the array
    private static void reverse(char[] str, int start, int end) {
        while (start < end) {
            char temp = str[start];
            str[start] = str[end];
            str[end] = temp;
            start++;
            end--;
        }
    }
    
    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 approach is O(n), where n is the length of the string. This is because we are iterating through the string a constant number of times. The space complexity is O(1) since we are modifying the string in place and not using any extra space proportional to the input size.

Edge Cases

Consider the following edge cases:

Empty string: The output should be an empty string.
String with multiple spaces: The algorithm should handle multiple spaces correctly.
Single word: The output should be the same as the input.

Testing

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

1. Input: "sky is blue" -> Output: "blue is sky"
2. Input: "hello world" -> Output: "world hello"
3. Input: "a b c" -> Output: "c b a"
4. Input: "" -> Output: ""
5. Input: "single" -> Output: "single"

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to break down the problem into smaller, manageable parts. Start with a simple solution and then optimize it. Practice similar problems to improve your problem-solving skills.

Conclusion

Reversing the words in a string is a common problem in text processing. Understanding and solving this problem helps in developing skills in string manipulation and algorithm optimization. Practice and explore further to master these concepts.

Reverse Words in a String II - Java Solution and Time Complexity Analysis