[LeetCode] 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".

click to show clarification.

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.

思路：

细节实现题。注意word的定义为前后有分隔的一段连续非空格字符。分隔可以是空格，也可以是字符串的前后边界。从后向前扫，根据空格逐个记录word，并反转append到结果中。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

class Solution { public: void reverseWords(string &s) { if(s.empty()) return; string ret, word; for(int i=s.size()-1; i>=0; i--) { if(isspace(s[i])) { if(i<s.size()-1 && !isspace(s[i+1])) { reverse(word.begin(),word.end()); ret.append(word+" "); word.clear(); } } else { word.push_back(s[i]); } } if(!isspace(s[0])) { reverse(word.begin(),word.end()); ret.append(word); } else if(!ret.empty()) { ret.pop_back(); } s = ret; } };

一遍扫描的解法：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public: void reverseWords(string &s) { string ret; int j = s.size(); for(int i=s.size()-1; i>=0; i--) { if(s[i]==' ') j = i; else if(i==0 || s[i-1]==' ') { if(!ret.empty()) ret.append(" "); ret.append(s.substr(i, j-i)); } } s = ret; } };