1021--RemoveOutermostParentheses

佚名 5年前 (2019-09-23) 算法 1380人围观抢沙发百度已收录

public class RemoveOutermostParentheses {
    /*
    解法一：栈，（ 进栈，） 出栈，栈为空时，则找到原语，然后去括号。
     */
    public String removeOuterParentheses(String S) {
        StringBuilder sb=new StringBuilder();
        Stack<Character> stack=new Stack<>();
        int start=0;    int end=0;
        for (int i=0;i<S.length();i++){
            char c=S.charAt(i);
            if (c=='('){
                stack.push(c);
            }
            if (c==')'){
                stack.pop();
                if (stack.isEmpty()){
                    end=i;
                    sb.append(S.substring(start+1,end));
                    start=end+1;
                }
            }
        }
     return sb.toString();
    }
    /*
    解法二：数字标记代替栈，从上面的代码中，我发现，栈起的作用并不是需要特定的括号，而只是判断是否为空来找原语。
            而进栈出栈又消耗时间，所以可以用一个整数来代替栈。
     */
    public String removeOuterParentheses2(String S) {
        StringBuilder sb=new StringBuilder();
        int flag=0;
        int start=0;    int end=0;
        for (int i=0;i<S.length();i++){
            char c=S.charAt(i);
            if (c=='('){
                flag++;
            }
            if (c==')'){
                flag--;
                if (flag==0){
                    end=i;
                    sb.append(S.substring(start+1,end));
                    start=end+1;
                }
            }
        }
        return sb.toString();
    }
    /*
    解法三：解法二优化：分析发现，并不需要用end来标记末尾，直接用i就可以了，快了1ms；
     */
    public String removeOuterParentheses3(String S) {
        StringBuilder sb=new StringBuilder();
        int start=0;
        int flag=0;
        for (int i=0;i<S.length();i++){
            char c=S.charAt(i);
            if (c=='('){
                flag++;
            }
            if (c==')'){
                flag--;
                if (flag==0){
                    sb.append(S.substring(start+1,i));
                    start=i+1;
                }
            }
        }
        return sb.toString();
    }
    /*
    解法四：最优解：判断的原理是和上面的一样的，但是上面的代码都是找到一个原语后，在原字符串上进行切割，比较费时间。
                    下面是挨个字符判断，如果满足条件，则直接添加。
     */
    public String removeOuterParentheses4(String S) {
       StringBuilder sb=new StringBuilder();
       int currentDepth=0;
       for (char c:S.toCharArray()){
           if (c=='('&&(currentDepth +=1)>1) sb.append(c);
           else if (c==')'&&(currentDepth -=1)>=1) sb.append(c);
       }
       return sb.toString();
    }
}