LeetCode 151. 翻转字符串里的单词（栈）

1. 题目信息

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

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"
示例 2：

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

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

说明：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-words-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

《剑指Offer》同题：面试题58 - I. 翻转单词顺序

2. 解题

• 利用栈先进后出
• 字符不为空，且不在最后一个位置时，加入字符串
• 字符不为空，且在最后一个位置时，加入字符串，并入栈
• 字符为空，如果当前字符串不为空，字符串入栈
• 最后依次输出栈顶，中间加空格，末尾没有空格

class Solution {
public:
    string reverseWords(string s) {
        while(!s.empty() && s.back()==' ')
            s.pop_back();
        while(!s.empty() && s.front()==' ')
            s.erase(s.begin());
        if(s.empty())
            return "";
        stack<string> stk;
        string str;
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] != ' ' && i != s.size()-1)
                str.push_back(s[i]);
            else if(s[i] != ' ' && i == s.size()-1)
            {
                str.push_back(s[i]);
                stk.push(str);
            }
            else
            {
                if(str != "")
                {
                    stk.push(str);
                    str = "";
                }
            }
        }
        str = "";
        while(!stk.empty())
        {
            str += stk.top();
            str.push_back(' ');
            stk.pop();
        }
        str.pop_back();
        return str;
    }
};

• 预先在s最后加一个空格，能简化代码

class Solution {
public:
    string reverseWords(string s) {
        while(!s.empty() && s.back()==' ')
            s.pop_back();
        while(!s.empty() && s.front()==' ')
            s.erase(s.begin());
        if(s.empty())
            return "";
        s.push_back(' ');//处理边界方便
        int i, n = s.size();
        string ans;
        stack<string> stk;
        for(i = 0; i < n; ++i)
        {
            if(s[i] != ' ')
                ans += s[i];
            else// (s[i]==' ')
            {
                if(ans.size())
                {
                    stk.push(ans);
                    ans.clear();
                }
            }
        }
        while(!stk.empty())
        {
            ans += stk.top()+' ';
            stk.pop();
        }
        ans.pop_back();
        return ans;
    }
};