Reverse Words in a String

Given a string s, reverse the order of its words (a word is a sequence of non-space characters). Leading/trailing/multiple spaces should collapse to a single space between words in the output. " the sky is blue " → "blue is sky the". (LeetCode 151)

1. Handling extra spaces. Use s.trim() to remove leading/trailing spaces, then split("\\s+") to split on one or more whitespace characters:

String[] words = s.trim().split("\\s+");

For s = " the sky is blue ", this gives ["the", "sky", "is", "blue"].

2. Reversing the words — two pointers. low starts at index 0, high at words.length - 1. Swap the words at low and high, then move low forward and high backward, repeating until they cross. This reverses in place in O(n) time without extra space.

int low = 0;
int high = words.length - 1;

while (low < high) {
    // Swap words[low] and words[high]
    String temp = words[low];
    words[low] = words[high];
    words[high] = temp;

    // Move pointers towards each other
    low++;
    high--;
}

3. Joining the words back into a sentence with String.join(" ", words).

class Solution {
    public String reverseWords(String s) {
        // Step 1: Trim and split the sentence into words based on spaces
        String[] words = s.trim().split("\\s+");

        // Step 2: Use two-pointer approach to reverse the array of words
        int low = 0;
        int high = words.length - 1;
        while (low < high) {
            String temp = words[low];
            words[low] = words[high];
            words[high] = temp;
            low++;
            high--;
        }

        // Step 3: Join the reversed words back into a sentence with a space separator
        return String.join(" ", words);
    }
}

Time: O(n) — splitting is O(n), reversing the word array is O(k) where k ≤ n, joining is O(n). Space: O(n), since the words live in an array.