Lesson 3: reverse word order

subject ：AcWing 77. Flip word order
Enter an English sentence , Words are separated by a space , There are no extra spaces at the beginning and end of the sentence .

Turn over the order of the words in the sentence , But the order of the characters in the word is the same .

For the sake of simplicity , Punctuation is treated like ordinary letters .

For example, input string "I am a student.“, The output "student. a am I”.

Data range
Input string length [0,1000].

Examples
Input ：

“I am a student.”

Output ：

“student. a am I”

Topic analysis ：
Method 1 ： Open up an extra space （ Time O(n), Space O(n)）
Go through the array , If you find a word, you insert the result array with forward interpolation , More trouble

class Solution {
    
public:
    string reverseWords(string s) {
    
        if(s.size()==0)return "";
        string res;
        string mid;
        for(auto it:s)
        {
    
            if(it==' ')
            {
    
                res=mid+" "+res;
                mid="";
            }else mid+=it;
        }
        res=mid+" "+res;
        res.pop_back();
        return res;
    }
};

Method 2 ： Two flips （ Time O(n), Space O(1)）
We can easily flip the entire string , After flipping , We can get the result by flipping each word

class Solution {
    
public:
    void reversestr(string &s,int l,int r)
    {
    
        while(l<r)swap(s[l],s[r]),l++,r--;
    }
    string reverseWords(string s) {
    
        reversestr(s,0,s.size()-1);
        for(int i=0;i<s.size();i++)
        {
    
            int j=i;
            while(j<s.size()&&s[j]!=' ')j++;
            reversestr(s,i,j-1);
            i=j;
        }
        return s;
    }
};