Reverse Words in a Sentence

Problem

Reverse the order of words in a sentence, collapsing extra spaces.

Input:  s = "  the sky is blue  "
Output: "blue is sky the"

Python Solution

def reverse_words(s):
    return " ".join(reversed(s.split()))

C++ Solution

string reverseWords(string s) {
    istringstream iss(s);
    vector<string> words;
    string word;
    while (iss >> word) words.push_back(word);
    reverse(words.begin(), words.end());
    string result;
    for (int i = 0; i < words.size(); i++) {
        result += words[i];
        if (i != words.size() - 1) result += " ";
    }
    return result;
}

Java Solution

class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split("\s+");
        StringBuilder result = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            result.append(words[i]);
            if (i != 0) result.append(" ");
        }
        return result.toString();
    }
}

Complexity

Time: O(n) — splitting, reversing the word list, and joining are each linear in the string's length. Space: O(n) — the list of words and the rebuilt string both take space proportional to the input.