題目描述

有效括號字符串為空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括號字符串，+ 代表字符串的連接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括號字符串。

如果有效字符串 S 非空，且不存在將其拆分為 S = A+B 的方法，我們稱其為原語（primitive），其中 A 和 B 都是非空有效括號字符串。

給出一個非空有效字符串 S，考慮將其進行原語化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括號字符串原語。

對 S 進行原語化分解，刪除分解中每個原語字符串的最外層括號，返回 S 。

示例

示例 1：

輸入："(()())(())"
輸出："()()()"
解釋：
輸入字符串為 "(()())(())"，原語化分解得到 "(()())" + "(())"，
刪除每個部分中的最外層括號后得到 "()()" + "()" = "()()()"。

示例 2：

輸入："(()())(())(()(()))"
輸出："()()()()(())"
解釋：
輸入字符串為 "(()())(())(()(()))"，原語化分解得到 "(()())" + "(())" + "(()(()))"，
刪除每隔部分中的最外層括號后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：

輸入："()()"
輸出：""
解釋：
輸入字符串為 "()()"，原語化分解得到 "()" + "()"，
刪除每個部分中的最外層括號后得到 "" + "" = ""。

提示：

• S.length <= 10000
• S[i] 為 "(" 或 ")"
• S 是一個有效括號字符串

解答

• 自己解答：

class Solution {
 public String removeOuterParentheses(String S) {
        Stack<Character> stack = new Stack<>();
        char c ;
        StringBuilder sum = new StringBuilder();
        for(int i=0;i<S.length();i++){
            c = S.charAt(i);
            if(stack.size()==1&&c==')'){
                stack.pop();
            }else if(stack.size()==1&&c!=')'){
                stack.push(c);
                sum.append(c);
            }else if(stack.size()>1&&c==')'){
                stack.pop();
                sum.append(c);
            }else if(stack.size()>1&&c=='('){
                stack.push(c);
                sum.append(c);
            }else if(stack.size()==0){
                stack.push(c);
            }
        }
        return sum.toString();
    }
}

• 熱門答案

class Solution {
    public String removeOuterParentheses(String S) {
        StringBuilder ans = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        int start = 0;// 初始化原語的起始位置
        int end = 0;// 初始化原語的結(jié)束位置
        boolean flag = false;// 標(biāo)志每個原語

        for (int i = 0;i < S.length();i++) {
            char ch = S.charAt(i);

            if (ch == '(') {// 遇到左括號，入棧
                stack.push(ch);
                if (!flag) {// 遇到的第一個左括號，是原語的開始位置，記錄下原語開始位置
                    start = i;
                    flag = true;
                }
            }

            if (ch == ')') {// 遇到右括號，出棧
                stack.pop();
                if (stack.isEmpty()) {// 當(dāng)?？盏臅r候，找到了一個完整的原語
                    end = i;// 記錄下結(jié)束位置
                    ans.append(S.substring(start + 1,end));// 去掉原語的最外層括號，并追加到答案中
                    flag = false;// 置標(biāo)志為false，往后接著找下一個原語
                    start = end;// 往后找，再次初始化原語開始位置
                }
            }
        }

        return ans.toString();
    }
}

• 性能對比