打字

按照时间顺序给出牛妹按下的键（以字符串形式给出,'<'代表回退backspace，其余字符均是牛妹打的字符，字符只包含小写字母与'<'），牛妹想知道最后在屏幕上显示的文本内容是什么。若为空则返回一个空串。

案例
输入："acv<"
返回值："ac"
说明： 前面三个字符串输入完后最后一个字符为回退所以答案为ac

方法一 STL队列

使用deque队列存储字符,遍历给定字符串如果当前遍历到字符则将字符存入队列中,如果遇到'<'时将队列中最后一个元素弹出最后将元素转为字符串输出即可

class Solution {
public:
    string Typing(string s) {
        // write code here
        deque<char> d; 
        for(int i = 0; i < s.size(); i ++){
            if(s[i] == '<'){ //如果遇到回退键
                if(d.size()) d.pop_back(); //判断序列中是否存在字符
            }else d.push_back(s[i]); //遇到字符则将字符存入序列中
        }
        string ans = "";
        while(d.size()) ans += d.front(), d.pop_front();
        return ans;
    }
};

时间复杂度: 遍历一遍字符串, deque的插入读取复杂度为
空间复杂度: 最多会产生大小存储字符串

方法二 数组模拟

思想与方法一大同小异定义一个数组和下标tot，对于每个回退将tot减少,字符则tot增加存入数组中,最后遍历一遍存入string中返回

class Solution {
public:
 char str[100010];
    string Typing(string s) {
        // write code here
        int tot = 0;
        for(int i = 0; i < s.length(); i ++){
            if(s[i] == '<' && tot > 0) tot --; //如果遇到回退符号则回退
            else if(s[i] != '<') str[++ tot] = s[i]; //记录答案
        }
        string ans = "";
        for(int i = 1; i <= tot; i ++) ans += str[i];
        return ans;
    }
};

时间复杂度: 遍历一遍字符串
空间复杂度: 存储整个字符串