删除最外层的括号

image.png

（力扣1021题）

解法一：暴力破解
思路：遍历字符串获取每一个字符，然后将左括号与右括号各自累加，如果左括号数目和右括号数目相同时就是一个原语，然后截取此字符串，放入list，最后再遍历list去除最外层括号，再拼接返回。注意：substring不包含endindex字符，需要+1。

  public String removeOuterParentheses(String s) {
            int len = s.length();
            //定义容器原语字符串
            List<String> list = new ArrayList();
            //记录左括号、右括号数目计数器
            int left = 0, right = 0, lastOpr = 0;
            //遍历字符串，读取到括号时对应计数器增加
            for (int i = 0; i < len; i++) {
                char c = s.charAt(i);
                if (c == '(') {
                    left++;
                } else if (c == ')') {
                    right++;
                }
                //检查是否到达某个原语结尾，截取原语子串添加到list
                if(left == right) {
                    list.add(s.substring(lastOpr, i + 1));
                    lastOpr = i + 1;
                }
            }
            StringBuilder str = new StringBuilder();
            for (String s1 : list) {
                String substring = s1.substring(1, s1.length() - 1);
                str.append(substring);
            }

            return str.toString();
        }

解法二：优化解法
思路：截取的时候不包含最外层括号

  public String removeOuterParentheses(String s) {
            int len = s.length();
            StringBuilder str = new StringBuilder();
            //记录左括号、右括号数目计数器
            int left = 0, right = 0, lastOpr = 0;
            //遍历字符串，读取到括号时对应计数器增加
            for (int i = 0; i < len; i++) {
                char c = s.charAt(i);
                if (c == '(') {
                    left++;
                } else if (c == ')') {
                    right++;
                }
                //检查是否到达某个原语结尾，截取原语子串添加到list
                if(left == right) {
                    str .append(s.substring(++lastOpr, i));
                    lastOpr = i + 1;
                }
            }
          
            return str.toString();
        }

解法三：
思路，栈

 class Stack<E> {
            Object[] elements = new Object[10000];
            int index = -1; //栈顶索引
            int size = 0; //元素个数
            public Stack() {

            }
            public void push(E e) {
                elements[++index] = e;
                size++;
            }

            public E peek() {
                if (index < 0) {
                    return null;
                }
                return (E)elements[index];
            }

            public E pop(){
                E e = peek();
                if (e != null) {
                    elements[index] = null;
                    index--; //栈顶下移
                    size--;
                }
                return e;
            }

            public  boolean isEmpty(){
                return size == 0;
            }
        }

        public String removeOuterParentheses(String s) {
            StringBuilder str = new StringBuilder();

            //使用数组模拟一个栈，临时存储字符，代替计数器
            Stack<Character> stack = new Stack<>();
            int lastOpr = 0;
            //遍历字符串
            for (int i = 0; i < s.length(); i ++) {
                char ch = s.charAt(i);
                //遇到左括号，入栈
                if (ch == '(') {
                    stack.push(ch);
                } else if (ch == ')') { //遇到右括号，出栈
                    stack.pop();
                }
                //判断栈是否为空，若为空，则找到了一个完整的原语
                if (stack.isEmpty()) {
                    str.append(s.substring(lastOpr + 1, i));
                    lastOpr = i + 1;
                }
            }
            return str.toString();
        }

解法四：直接用数组代替栈

public String removeOuterParentheses(String s) {
            StringBuilder str = new StringBuilder();

            //使用数组模拟一个栈，临时存储字符，代替计数器
            char[] stack = new char[s.length()];
            //栈顶索引
            int index = -1;
            int lastOpr = 0;
            //源字符串转数组，遍历字符串
            char[] chars = s.toCharArray();
            for (int i = 0; i < s.length(); i ++) {
                char ch = chars[i];
                //遇到左括号，入栈
                if (ch == '(') {
                    //读到左括号，在数组之前有数据，则入原语
                    if (index > -1) {
                        str.append(ch);
                    }
                    stack[++index] = ch;
                } else { //遇到右括号，出栈
                    stack[index--] = '\u0000';
                    if (index > -1) {
                        str.append(ch);
                    }
                }

            }
            return str.toString();
        }