题解 | #字符串变形#

方法一：栈
核心思想：
题目要求将单词逆序输出，很容易想到一个思路就是利用栈的先入后出特性。
解法：首先读取单词，以空格为分界符（在字符串最后加上一个空格避免特判），读取的同时进行大小写转换，然后将单词加入到栈中。在全部单词读取完毕后，逐个弹出单词，即为答案
图示：

之后从栈顶逐个弹出即为答案
核心代码：

class Solution {
public:
    string trans(string s, int n) {
        stack<string> sk;
        string str;
        s.push_back(' ');//避免特判
        for(int i = 0; i <= n; ++i) {//注意此时单词长度为n+1
            if(s[i] == ' ') {
                sk.push(str);//以空格为界进行压栈
                str = ""; 
            } else {
                if(s[i] >= 'a' && s[i] <= 'z') { 
                    str += (s[i] - 'a' + 'A'); 
                } else { 
                    str += (s[i] - 'A' + 'a'); 
                } 
            }
        } 
        string ans; 
        while(!sk.empty()) { 
            //从栈中逐个弹出单词 
            ans += sk.top(); sk.pop(); 
            ans.push_back(' '); 
        } 
        ans.pop_back();//去除最后一个单词后的空格 
        return ans;
    }
};

复杂度分析：
时间复杂度：$O（n),$需要对单词进行读取以及弹出，两个操作时间复杂度都为O(n)
空间复杂度：$O（n）$，需要额外的栈空间存储单词，以及存储转换后单词的字符串

方法二：两次翻转
核心思想：

核心代码：

class Solution {
public:
    string trans(string s, int n) {
         reverse(s.begin(), s.end());//将整个字符串进行翻转
        int i = 0, j = 0;
        while(i < n) { 
            j = i; 
            while(j < n && s[j] != ' ') { 
                //读取一个单词并同时进行大小写转换 
                if(s[j] >= 'a' && s[j] <= 'z') { 
                    s[j] += ('A' - 'a'); 
                } else { 
                    s[j] += ('a' - 'A'); 
                } 
                ++j; 
             }
            reverse(s.begin() + i, s.begin() + j);//翻转这个单词 
            i = j + 1; 
        }
        return s;
    }
};

复杂度分析：
时间复杂度：$O（n)$,相对于需要对整个字符串进行两次读取（翻转）
空间复杂度：$O（1）$，只使用了常数个变量