151. Reverse Words in a String

Intuition

We are given a string that may contain leading, trailing, or multiple intermediate spaces. We need to reverse the order of words, not the characters, and return a well-formatted string where:

• Words are in reverse order.

• Words are separated by a single space.

• No leading or trailing spaces are allowed.

So

• Trim the input string to remove leading and trailing whitespace.

• Split the string into words based on space.

• Reverse the array of words.

• Use a StringBuilder to join words together with a single space, skipping empty strings caused by multiple spaces.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(N)$

Code

public String reverseWords(String input) {
    // Step 1: Trim input to remove leading/trailing spaces and split by space
    String[] words = input.trim().split(" ");

    // Step 2: Reverse the array of words
    for (int left = 0, right = words.length - 1; left < right; left++, right--) {
        String temp = words[left];
        words[left] = words[right];
        words[right] = temp;
    }

    // Step 3: Build the final string, skipping extra spaces (i.e., empty strings)
    StringBuilder reversedSentence = new StringBuilder();
    for (int i = 0; i < words.length; ++i) {
        if (words[i].isEmpty()) continue; // Skip empty strings from multiple spaces
        if (reversedSentence.length() != 0) reversedSentence.append(" ");
        reversedSentence.append(words[i]);
    }

    return reversedSentence.toString(); // Return the cleaned, reversed sentence
}