# 151-Reverse Words in a String
###### tags: `Medium`
## Question
https://leetcode.com/problems/reverse-words-in-a-string/
## Key
1. 遇到word就記下來等到" "就存到vector，再反過來輸出到output
2. 最麻煩的是不測試不知道要處理input可能有前後都有空格的情況
## Reference
## Solution

class Solution {
public:
    string reverseWords(string s) {
        
        stack<string> st;
        string word = "";
        string res = "";
        
        s = trim(s);
        s += ' ';
        
        for(char ch : s)
        {
            if(ch ==  ' ')
            {
                st.push(word);
                word = "";
            }
            else
                word += ch;
        }
        
        while(!st.empty())
        {
            res += " " + st.top();
            st.pop();
        }
        
        return res.substr(1);
    }
    
    string trim(string s)
    {
        string res = "";
        int i=0;
        while(i < s.size())
        {
            res.push_back(s[i]);
            if(s[i] == ' ' && (i < s.size() && s[i+1] == ' '))
            {
                while(i < s.size() && s[i+1] == ' ')
                    i++;
            }
            i++;
        }
        
        if(res[0] == ' ')
            res.erase(res.begin());
        if(res.back() == ' ')
            res.erase(res.end()-1);
        return res;
    }
};

### use reverse function

class Solution {
  public:
  string reverseWords(string s) {
    // reverse the whole string
    reverse(s.begin(), s.end());

    int n = s.size();
    int idx = 0;
    for (int start = 0; start < n; ++start) {
      if (s[start] != ' ') {
        // go to the beginning of the word
        if (idx != 0) s[idx++] = ' ';

        // go to the end of the word
        int end = start;
        while (end < n && s[end] != ' ') s[idx++] = s[end++];

        // reverse the word
        reverse(s.begin() + idx - (end - start), s.begin() + idx);

        // move to the next word
        start = end;
      }
    }
    s.erase(s.begin() + idx, s.end());
    return s;
  }
};