题目：
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".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.
解题思路： 先整体翻转，在把单词一个个翻转。（或反过来也行）
代码也许还能优化:
class Solution {
public:
void reverseWords(string &s) {
if(s == "") return;
if(s.length() == popBlankLead(s)) return;
else if(popBlankTrail(s) < 0) return;
int judge = 0;
while(judge < s.length() && s[judge] != ' ') ++judge;
if(judge == s.length()) return;
reverseAlpha(s, 0, s.length() - 1);
int start = 0;
for(int end = 0; end < s.length(); ++end){
if(s[end] == ' '){
while(s[end + 1] == ' '){
s.erase(end, 1);
}
reverseAlpha(s, start, end - 1);
start = end + 1;
}
}
reverseAlpha(s, start, s.length() - 1);
}
void reverseAlpha(string &s, int begin, int end){
if(s == "" || begin >= end) return;
int mid = (end + begin +1) >> 1;
for(int i = begin; i < mid; ++i){
char c = s[i];
s[i] = s[end];
s[end--] = c;
}
}
int popBlankLead(string &s){
int first = 0;
while(s[first] == ' ' && first < s.length()) ++first;
s.erase(0, first);
return first;
}
int popBlankTrail(string &s){
int end = s.length() - 1;
while(s[end] == ' ' && end >= 0) --end;
s.erase(end + 1,s.length() - end - 1);
return end;
}
};
精简版代码：
class Solution {
public:
void reverseWords(string &s) {
string buf;
stringstream ss(s);
vector<string> tokens;
while (ss >> buf) tokens.push_back(buf);
if (tokens.size() == 0) s="";
else{
int n = tokens.size()-1;
s = tokens[n];
for (int i = n-1; i >=0; -- i) s+=" "+tokens[i];
}
}
};