151. Reverse Words in a String

The idea is to reverse the whole string first and reverse each word in the string. However, we need to preprocess the string first to get a "clean" one, i.e. no leading and trailing spaces and no extra spaces between two words.

1:  class Solution {  
2:  public:  
3:    void reverseWords(string &s) {  
4:      preprocess(s);  
5:      reverse(s.begin(), s.end());  
6:      int i = 0, j = 0;  
7:      for (; i < s.size(); i++) {  
8:        if (s[i] == ' ') {  
9:          reverseWord(s, j, i-1);  
10:          j = i+1;  
11:        }  
12:      }  
13:      if (j != s.size()) reverseWord(s, j, s.size()-1);  
14:    }  
15:    void reverseWord(string &s, int i, int j) {  
16:      while (i < j) {  
17:        swap(s[i++], s[j--]);  
18:      }  
19:    }  
20:    void preprocess(string &s) {  
21:      int i = 0, j = 0;  
22:      for (; i < s.size(); i++) if (s[i] != ' ') break;  
23:      if (i != 0) s.erase(s.begin(), s.begin()+i);  
24:      for (i = s.size()-1; i >= 0; i--) if (s[i] != ' ') break;  
25:      if (i != s.size()-1) s.erase(s.begin()+i+1, s.end());  
26:      for (i = 0, j = 0; i < s.size(); i++) {  
27:        if (s[i] == ' ') {  
28:          j = i+1;  
29:          while (s[j] == ' ') j++;  
30:          if (j != i+1) s.erase(s.begin()+i+1, s.begin()+j);  
31:        }  
32:      }  
33:    }  
34:  };  

When I revisited this problem, I combined reversing single word and eliminating redundant spaces into one loop. I made mistakes in
line 21: I only need to delete redundant spaces which means i-j>1
line 22: For next loop, j must point to the beginning letter of the word.

1:  class Solution {  
2:  public:  
3:    void reverseWords(string &s) {  
4:      if (s.empty()) return;  
5:      // trim leading spaces  
6:      int i = 0, j = 0;  
7:      while (i < s.size() && s[i] == ' ') i++;  
8:      s = s.substr(i);  
9:      // trim tailing spaces  
10:      i = s.size() - 1;  
11:      while (i >= 0 && s[i] == ' ') i--;  
12:      s = s.substr(0, i+1);  
13:      reverse(s.begin(), s.end());  
14:      i = 0, j = 0;  
15:      while (i < s.size()) {  
16:        while (i < s.size() && s[i] != ' ') i++;  
17:        reverse(s.begin()+j, s.begin()+i);  
18:        j = i;  
19:        while (i < s.size() && s[i] == ' ') i++;  
20:        if (i - j > 1) s.erase(s.begin()+j, s.begin()+i-1);  
21:        i = ++j;  
22:      }  
23:    }  
24:  };