Reverse Words in a String

Split, Reverse, Join — Watch the three phases: splitting the string into a word array, reversing that array in place, and joining the reversed words into the final result.

class Solution {
public:
    string reverseWords(string s) {
        // Split into words
        vector<string> words;
        istringstream iss(s);
        string word;
        while (iss >> word) {
            words.push_back(word);
        }
        
        // Reverse the word list
        reverse(words.begin(), words.end());
        
        // Join with single space
        string result;
        for (int i = 0; i < words.size(); i++) {
            if (i > 0) result += " ";
            result += words[i];
        }
        return result;
    }
};

class Solution:
    def reverseWords(self, s: str) -> str:
        # split() handles multiple spaces, leading/trailing spaces
        words = s.split()
        # Reverse and join with single space
        return " ".join(words[::-1])

class Solution {
    public String reverseWords(String s) {
        // Trim and split on one or more spaces
        String[] words = s.trim().split("\\s+");
        
        // Reverse the array
        int left = 0, right = words.length - 1;
        while (left < right) {
            String temp = words[left];
            words[left] = words[right];
            words[right] = temp;
            left++;
            right--;
        }
        
        // Join with single space
        return String.join(" ", words);
    }
}

Two-Phase Reversal: Entire String, Then Each Word — Watch the elegant two-phase trick: first reverse the whole string (putting words in the right order but backwards), then reverse each individual word to fix the spelling.

class Solution {
public:
    string reverseWords(string s) {
        // Step 1: Clean up spaces and compact
        int n = s.size();
        int write = 0;
        for (int read = 0; read < n; read++) {
            if (s[read] != ' ') {
                if (write > 0) s[write++] = ' ';
                while (read < n && s[read] != ' ') {
                    s[write++] = s[read++];
                }
            }
        }
        s.resize(write);
        n = write;
        
        // Step 2: Reverse entire string
        reverse(s.begin(), s.end());
        
        // Step 3: Reverse each word
        int start = 0;
        for (int i = 0; i <= n; i++) {
            if (i == n || s[i] == ' ') {
                reverse(s.begin() + start, s.begin() + i);
                start = i + 1;
            }
        }
        
        return s;
    }
};

class Solution:
    def reverseWords(self, s: str) -> str:
        # Convert to list for mutability
        chars = list(s)
        
        # Step 1: Clean up spaces - compact to single spaces, no leading/trailing
        write = 0
        n = len(chars)
        read = 0
        while read < n:
            if chars[read] != ' ':
                if write > 0:
                    chars[write] = ' '
                    write += 1
                while read < n and chars[read] != ' ':
                    chars[write] = chars[read]
                    write += 1
                    read += 1
            else:
                read += 1
        chars = chars[:write]
        
        # Step 2: Reverse entire array
        chars.reverse()
        
        # Step 3: Reverse each word
        start = 0
        for i in range(len(chars) + 1):
            if i == len(chars) or chars[i] == ' ':
                # Reverse chars[start:i]
                left, right = start, i - 1
                while left < right:
                    chars[left], chars[right] = chars[right], chars[left]
                    left += 1
                    right -= 1
                start = i + 1
        
        return ''.join(chars)

class Solution {
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        
        // Step 1: Clean up spaces
        int write = 0;
        for (int read = 0; read < n; read++) {
            if (chars[read] != ' ') {
                if (write > 0) chars[write++] = ' ';
                while (read < n && chars[read] != ' ') {
                    chars[write++] = chars[read++];
                }
            }
        }
        
        // Step 2: Reverse entire cleaned portion
        reverse(chars, 0, write - 1);
        
        // Step 3: Reverse each word
        int start = 0;
        for (int i = 0; i <= write; i++) {
            if (i == write || chars[i] == ' ') {
                reverse(chars, start, i - 1);
                start = i + 1;
            }
        }
        
        return new String(chars, 0, write);
    }
    
    private void reverse(char[] chars, int left, int right) {
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }
}