LeetCode | 151. 翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

实现代码：

class Solution {
public:
    //栈1
    /*
    时间复杂度：O(n)
    空间复杂度：O(n)  
    */
    string reverseWords(string s) {
        istringstream is(s);
        stack<string>st;
        //可以改用vector<string>
        string str, res;
        while (is >> str) {
            st.push(str);
        }
        while (!st.empty()) {
            if (!res.empty())
                res += " ";
            res += st.top();
            st.pop();
        }
        return res;
    }
    //reverse
    /*
    时间复杂度：O(n)
    空间复杂度：O(1)  
    */
    string reverseWords(string s) {
        string res;
        for (int i = 0; i < s.size(); ++i) {
            string temp;
            while (i < s.size() && s[i] == ' ') ++i;
            while (i < s.size() && s[i] != ' ')  temp += s[i++];
            if (!temp.empty()) {
                reverse(temp.begin(), temp.end());//对单词反转
                if (!res.empty())res += ' ';
                res += temp;
            }
        }
        reverse(res.begin(), res.end());//对句子反转
        return res;
    }
};