Leetcode 151. Invert words in string

subject

Give you a string s , Invert the string word The order of .

word Is a string of non whitespace characters .s Use at least one space in the string word Separate .

return word Reverse order and word The result string connected with a single space .

Be careful ： Input string s There may be leading spaces in 、 Trailing spaces or multiple spaces between words . In the returned result string , Words should be separated by only a single space , And does not contain any additional spaces .

Ideas

• First, remove all redundant spaces in the word
• Then flip the entire string
• Then look for the beginning and end subscripts of each word from the beginning , Flip each word

Code

class Solution {
    
public:
    string reverseWords(string s) {
    
        removeExtraSpaces(s);//  Remove redundant spaces 
        reverse(s,0,s.size() - 1);//  Invert all strings 
        for(int i = 0; i < s.size(); i++)
        {
    
            //  Assign the first subscript of a word to j
            int j = i;
            // Find spaces between words   Flip Words 
            while(j < s.size() && s[j] != ' ') j++;
            // j Until the space position stops 
            reverse(s,i,j - 1);
            i = j;//  At this time, the subscript at the space position is given i

            //  But the next step i++ i Point to the beginning and end of the next word 
        }
        return s;
    }

    void reverse(string &s,int start,int end)
    {
    
        for(int i = start,j = end; i < j; i++,j--)
        {
    
            //  Define the beginning and end pointers   Direct exchange 
            swap(s[i],s[j]);
        }
    }

    void removeExtraSpaces(string& s){
    
        //  Remove the space in the string 
        int slowIndex = 0,fastIndex = 0;//  Define speed pointer 

        //  Remove the space before the string 
        while(s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ')
        {
    
            fastIndex++;
        }

        for(; fastIndex < s.size(); fastIndex++)
        {
    
            //  Remove redundant spaces in the middle of the string 
            if(fastIndex - 1 > 0 && s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' ')
            {
    
                continue;//  If both the current character and the previous character are spaces   So directly continue
            }
            else
            {
    
                s[slowIndex] = s[fastIndex];
                slowIndex++;//  Use non space characters to cover directly forward 
            }
        }

        if(slowIndex - 1 > 0 && s[slowIndex - 1] == ' ')
        {
    
            //  Remove the space at the end of the string 
            s.resize(slowIndex - 1);
        }
        else
        {
    
            s.resize(slowIndex);//  Reset string size 
        }
    }
};