[Leetcode] Reverse Words in a String, Solution

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.

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.

[Thoughts]
这是比较琐碎的一道实现题。先把字符串中的多余空格清除掉，然后对于每一个word做reverse，最后再对整个string做一遍reverse即可。


[Code]
注意，这里remove multiple spaces的循环和swap words的循环，可以merge成一个loop，这里分成两个是为了保证可读性。

1:    void reverseWords(string &s) {  
2:      int start = 0;  
3:      int end = 0;  
4:      string sn="";  
5:        
6:      // remove the multiple space  
7:      for(int i =start; i< s.size();){  
8:        if(s[i] == ' ') {  
9:          sn.push_back(' ');  
10:          while(i < s.size() && s[i] ==' ') {  
11:            i++;  
12:          }  
13:        } else {  
14:          sn.push_back(s[i]);  
15:          i++;  
16:        }  
17:      }  
18:      s = sn;  
19:        
20:      // swap the words  
21:      while(end < s.size()) {  
22:        while(end < s.size() && s[end] ==' ') {  
23:          start ++;  
24:          end++;  
25:        }  
26:          
27:        while(end < s.size() && s[end] != ' ') end++;  
28:          
29:        swapW(s, start, end-1);  
30:        start = end;  
31:      }  
32:        
33:      swapW(s, 0, s.size()-1);  
34:        
35:      //remove the leading or trailing spaces  
36:      start = s[0] == ' '? 1:0;  
37:      end = s[s.size()-1] == ' '? s.size()-2: s.size()-1;  
38:      s= s.substr(start, end-start +1);  
39:    }  
40:      
41:    void swapW(string& s, int start, int end) {  
42:      for(int i =start, j = end; i<j; i++, j--) {  
43:        swap(s[i],s[j]);  
44:      }  
45:    }