题解 | #打字#

思路：

题目的主要信息：

• 顺序输入字符，存在字符串s中
• 如果输入的是'<'，则回退一格，相当于删除当前输入的最末尾字符，如果当前输入为空不操作
• 输入只包含小写字母和'<'，问最后的结果是什么

方法一：数组过程模拟
具体做法：
使用数组临时存储所有字符，遍历字符串s，如果遇到'<'且数组为空，则不操作，遍历下一个；如果遇到'<'且数组不为空，则删除末尾元素；否则，字符加入数组的末尾。
最后将数组中的元素存入string。

class Solution {
public:
    string Typing(string s) { 
        vector<char> temp; //记录输入内容
        for(int i = 0; i < s.length(); i++){
            if(temp.size() == 0 && s[i] == '<')  //输入内容为空且回退
                continue;
            else if(s[i] == '<') //回退
                temp.pop_back();
            else
                temp.push_back(s[i]); //输入
        }
        string res = "";
        for(int i = 0; i < temp.size(); i++) 
            res += temp[i];
        return res;
    }
};

复杂度分析：

• 时间复杂度：，n为字符串s的长度，两次遍历，第二次不大于
• 空间复杂度：，最坏情况没有回退，临时数组存储所有字符

方法二：栈
具体做法：
所有字符用栈来保存，空斩遇到回退不操作，否则遇到回退弹出栈顶，其他情况字符入栈。
最后将栈中元素逆序相加即可。

class Solution {
public:
    string Typing(string s) { 
        stack<char> st;
        for(int i = 0; i < s.length(); i++){
            if(st.empty() && s[i] == '<')  //输入内容为空且回退
                continue;
            else if(s[i] == '<') //回退
                st.pop();
            else
                st.push(s[i]); //输入
        }
        string res = "";
        while(!st.empty()){  //逆转相加
            res = st.top() + res;
            st.pop();
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，n为字符串s的长度，两次遍历，第二次不大于
• 空间复杂度：，最坏情况没有回退，栈存储所有字符