题意

一个字符串表示一段打字序列，其中如果字符为"<",则表示删除了最后一个字符

求最终的字符串

给定的字符串长度$\le 10^5\backslash leq\; 10^5$

方法

朴素实现

我们把题目直接逐句转化成代码

依次遍历字符串s，如果当前是"<" 则把结果字符串的最后一位删除l = l[:-1],否则把字符加到结果字符串的末端l = l+s[i]

最后输出最终字符串即可

代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return string字符串
#
class Solution:
    def Typing(self , s ):
        l = ""
        for i in range(len(s)):
            if s[i] == '<' :
                l = l[:-1]
            else:
                l = l + s[i]
        return l

复杂度分析

时间复杂度: 我们对s进行了遍历，每次对结果字符串末尾进行增删，增删的代价如果为常数，那么总时间复杂度为$O(len(s))O(len(s))$

空间复杂度: 我们只用了l记录最终字符串，和一些其它临时变量，所以空间复杂度为$O(len(s))O(len(s))$

反向处理

我们输入了字符，遇到了删除键需要删除。

题目给了我们正的顺序。但实际上我们一次拿到了整个输入序列

我们把输入序列倒过来

以题目的样例为例

"acv<"

正向的场景是

下面我们如果反过来看这个事情

这样我们仅需要一个变量来记录高位删了几次，遇到"<",次数加一，遇到字符次数减一，当次数为零时，才会被添加到字符串里

代码如下

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string Typing(string s) {
        int n = s.length();
        int delcnt = 0;
        string r ;
        for(int i = n-1;i>=0;i--){
            if(s[i] == '<')delcnt++;
            else if(delcnt)delcnt--;
            else r+=s[i];
        }
        reverse(r.begin(),r.end());
        return r;
    }
};

时间复杂度: 我们对s进行了遍历，每次对结果字符串末尾进行增删,或删除量加减1，那么总时间复杂度为$O(len(s))O(len(s))$

空间复杂度: 我们只用了r记录最终字符串，和一些常数个临时变量，所以空间复杂度为$O(len(s))O(len(s))$