## Monday, August 7, 2017

### [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.
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]

[Code]

``````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:    }
``````