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.

# 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--;
}
}

};
``````