Reverse Words in a String

LeetCode #151

Description:

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

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.

Example:

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

Idea:

reverse each word, then reverse the whole sentence.

但是，处理各种heading， training和多余的spacing很难。

Code:

class Solution {
public:

    void reverseWords(string &s) {
        int i=0, j; // left and right of one word
        int icurr=0; // current copy position
        int n=s.size();
        int count=0; // how many words has been copied

        while(i!=n){
            while(i!=n && s[i]==' '){ // Until non space is found
                ++i;
            }
            j=i;
            while(j!=n && s[j]!=' '){ // Until space is found
                j++;
            }

            if(i!=n){
                reverseSingleWord(s, i, j-1); // reverse one word
                count++;
            }

            if(count>1 && i!=n){ //如果不是第一个word或者i已经到头了
                icurr++;
            }

            while(i!=j){ // Copy one word
                s[icurr++] = s[i++];
            }

            if(icurr!=n){ // Avoid out of range
                s[icurr]=' '; // Set one space between words
            }
        }

        s.erase(icurr);

        reverseSingleWord(s, 0, s.size()-1); // reverse the whole sentence

    }

    void reverseSingleWord(string &s, int i, int j){
        while(i<j){
            swap(s[i], s[j]);
            i++;
            j--;
        }
    }

};