leetcode:Reverse Words in a String

一、 題目

給出一個字符串，以單詞為單位反轉字符串。

例如 i am echo

返回 echo am i

二、 分析

仔細分析會發現，對於中間結果我們需要保存，即我們得保證以單詞為單位。另外我們需要考慮到下面的情況

1、中間有多個空格的處理

2、沒有空格的字符串

3、反轉後開頭和結尾不能有空格

4、最後的結果單詞間得有空格

所以，由以上我們有兩種思路，一種就是以單詞為單位反轉，這個需要用到vector，reverse即可，需要兩次for循環，如下：

class Solution {
public:
    void reverseWords(string &s) {
        vector des;
        if(s.empty())
            return;
        int len = s.size();
        for(int i = 0; i < len; i++){
            if(s[i] == ' ')
                continue;
            string word;
            while(i < len && s[i] != ' '){
                word += s[i];
                i++;
            }
            des.push_back(word);
        }
        reverse(des.begin(), des.end());
        if(des.empty())
            s = "";
        else {
            s.clear();
            int j ;
            for(j = 0; j < des.size() -1; j++){
                s += des[j];
                s += ' ';
            }
            s += des[j];    
        }
    }
};

另一種思路是使用特殊的存儲結構——棧，那麼此時我們就不需要再反轉了，直接順序保存即可，代碼如下：

class Solution {
public:
    void reverseWords(string &s) {
        stack des;
        if(s.empty())
            return;
        int len = s.size();
        for(int i = 0; i < len; i++){
            if(s[i] == ' ')
                continue;
            string word;
            while(i < len && s[i] != ' '){
                word += s[i];
                i++;
            }
            des.push(word);
        }
        if(des.empty())
            s = "";
        else {
            s.clear();
            int j ;
            int length = des.size();
            for(j = 0; j < length -1; j++){
                s += des.top();
                des.pop();
                s += ' ';
            }
            s += des.top();
        }
    }
};