LeetCode: Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

---

We can achieve this by reverse each word first and then reverse the whole string. Here is a example:

string: "the sky is blue"

Reverse each word: "eht yks si eulb"

Reverse the whole string: "blue is sky the"

C++ Code:

/*
 * func: reverse_words
 * goal: reverse the string word by word
 * @param s: input string s
 * return:
 */
/*
 * reverse each word first and then reverse the whole string
 * complexity: time O(n), space O(n)
 */
void reverse_words(string &s){
    string word = "";
    string intermediate = "";
    for(const char &ch : s){
        if(ch == ' '){
            if(word.length() > 0){
                reverse(word.begin(), word.end());
                intermediate += word + " ";
            }
            word.clear();
        }else{
            word += ch;
        }
    }
    if(word.length() > 0){
        reverse(word.begin(), word.end());
        intermediate += word;
    }else{
        size_t space = intermediate.find_last_of(" ");
        if(space != string::npos)
            intermediate.erase(space);
    }
    //Reverse the whole string
    reverse(intermediate.begin(), intermediate.end());
    s = intermediate;
}

Python Code:

# func: reverse words in the string
# @param s: input string
# @return: reversed string
def reverse_words(s):
    words = s.split(" ")
    intermediate = ""
    for word in words:
        if word:
            intermediate += word[::-1] + ' '
    return intermediate[-2::-1]