151 - Reverse Words In A String

#medium

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

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

Solution 1 - Reverse whole string then reverse word by word - O(1) in Space Complexity

class Solution {
public:
    string reverseWords( string s ) {
        reverse(s.begin(), s.end());
        // i = iterator, j = original position to end position
        int i = 0, j = 0, n = s.size(), lastIndex;
        while ( i < n ) {
			       int startIndex = j
             // 跳過空格
             while ( i < n && s[i] == ' ' ) i++;

						 // reverse a word (in a big string).
             while ( i < n && s[i] != ' ' ) {
                 s[j++] = s[i++];
                 lastIndex = j;  // j從單字開始到結尾。
             }

            reverse(s.begin() + startIndex, s.begin() + lastIndex);
            s[j++] = ' '; // 加入空白
        }

        // Resize the string to the last index of the last word: to avoid empty spaces at the end.
        s.resize(lastIndex);
        return s;
    }
};

Solution 2

class Solution {
public:
    string reverseWords( string s ) {
        stringstream ss;
        ss << s;
        string word, ans;
        while ( ss >> word ) {
            ans = word + " " + ans;
        }

        ans = ans.substr(0, ans.size() - 1 );
        return ans;
    }
};