557. 反转字符串中的单词 III

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例:

输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc"
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

思路

维护一个栈，单词先不断压栈，等到遇到空格的时候，再把栈依次弹出。不要忘记最后需要额外清空一次栈

性能分析

时间复杂度O(N)，空间复杂度，由于要维护一个栈，所以额外耗费为O(bigestLength)，最坏情况下为O(N)

具体代码

string reverseWords(string s) {
    stack<char> st; // 单词栈
    string res = ""; // 结果集
    for(int i = 0; i < s.size(); i++){ // 遍历整个字符串
        if(s[i] == ' '){ // 空格->执行弹栈清栈
            while(!st.empty()){
                res += st.top();
                st.pop();
            }
            res += s[i]; // 追加空格
        }
        else{ // 非空格->入栈
            st.push(s[i]);
        }
    }
    while(!st.empty()){ // 额外的弹栈清栈
        res += st.top();
        st.pop();
    }
    return res;
}