题解 | #打字#_牛客博客

题意整理

给定输入字符串，按规则打印出来。
如果不是'<'，正常打印，如果是'<'并且前面字符不为空，则删除上一次打印的字符。

方法一（栈）

1.解题思路

用栈记录每次打印的字符，如果当前字符是'<'，并且栈不为空，则弹出栈顶元素。最后将栈中所有元素返回。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String Typing (String s) {
        //初始化栈和可变字符串
        LinkedList<Character> stack=new LinkedList<>();
        StringBuilder sb=new StringBuilder();

        for(char c:s.toCharArray()){
            //如果不是'<'就添加
            if(c!='<'){
                stack.push(c);
            }
            //如果是'<'并且不为空，就回退
            else{
                if(!stack.isEmpty()){
                    stack.pop();
                }
            }
        }

        //将栈中字符添加到可变字符串sb
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }

        return sb.reverse().toString();
    }
}

3.复杂度分析

时间复杂度：需要遍历一次输入字符串，以及取出栈中所有元素，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外大小为n的栈，所以空间复杂度是 $O(n)$ 。

方法二（模拟）

1.解题思路

初始化一个可变字符串，如果当前不是'<'就添加，如果是，并且之前字符串不为空就回退。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String Typing (String s) {
        //新建可变字符串
        StringBuilder sb=new StringBuilder();
        for(char c:s.toCharArray()){
            //如果不是'<'就添加
            if(c!='<'){
                sb.append(c);
            }
            //如果是'<'并且不为空，就回退
            else{
                if(sb.length()>0){
                    sb.deleteCharAt(sb.length()-1);
                }
            }
        }
        return sb.toString();
    }
}

3.复杂度分析

时间复杂度：需要遍历一次输入字符串，所以时间复杂度是 $O(n)$ 。
空间复杂度：不需要额外的空间，所以空间复杂度是 $O(1)$ 。