Simple two-step C++ solution


  • 0
    D
    class Solution {
    public:
        void reverseWords(string &s) {
            int len = s.size()+1, i=0, head=-1, tail = 0, wrt=0;
            s.push_back(' '); // add an extra space to make sure the last word is reversed in the first step
            //two-step method, first reverse each word and clean the extra white spaces 
            while(i<len)
            {
                if(isspace(s[i])) 
                {
                    if(head>=0) // currently search the end of a new word
                    { // which means, this is the end of a new word
                        tail = wrt-1;
                        while(head<tail) swap(s[tail--], s[head++]); // reverse the new word
                        s[wrt++] = ' ';
                        head = -1; // indicate in search of the begin of a new word
                    }
                    ++i; //skip the space
                }
                else{ // if it is not a space character
                    if(head<0) head = wrt; // if it is a new word, save head;
                    s[wrt++] = s[i++]; // remove extra space
                }
            }
    
            //second step:  reverse the whole string
            len = wrt==0?0:--wrt; // be careful about the corner case, all space string
            for(tail = --wrt, head =0; head<tail; ++head, --tail) swap(s[head], s[tail]);
            s.resize(len);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.