151. Reverse Words in a String

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

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

Update (2015-02-12):

For C programmers: Try to solve it in-place in O(1) space.

题意：把句子逆置。

思路：思路比较多，允许把word从后向前一个一个的取出，然后输出；也可以一个个word取出，再逆置输出。我采用的是大逆置，加上word范围的小逆置。

class Solution {
public:
	void reverseWords(string &s) {
		if (s.empty())
			return;
		int i = 0;
		while (i < s.size() && s[i] == ' '){ i++; }
		if (i == s.size()){
			s.clear();
			return;
		}
		s = s.substr(i);
		reverse(s.begin(), s.end());
		i = 0;
		while (i < s.size() && s[i] == ' '){ i++; }
		s = s.substr(i);
		for (i = 1; i < s.size(); i++){
			if (s[i] == ' ' && s[i - 1] == ' '){
				s.erase(i,1);
				i--;
			}
		}
		int p = 0;
		size_t q = s.find_first_of(' ', p);
		while (q != string::npos){
			reverse(s.begin() + p, s.begin() + q);
			p = q + 1;
			q = s.find_first_of(' ', p);
		}
		reverse(s.begin() + p, s.end());
	}
};