leetcode刷题 [java] 1021. 删除最外层的括号

有效括号字符串为空 ("")、"(" + 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 是一个有效括号字符串

三种解题思路
解法一 : 计数法（找规律）
基本思路：设置一个计数器 count，左括号 +1，右括号减 1，等于 0 则找到外括号的终点。并且 0 后面的一个括号肯定也是外括号，可以直接跳过。

i	count
(	1
(	2
(	3
)	2
)	1
)	0
(	1
)	0
(	1
)	0

代码如下：

class Solution {
    public String removeOuterParentheses(String S) {
        int count = 0;
        int i_1 = 0;
        int j_1 = 0;
        StringBuffer s = new StringBuffer();
        for(int i = 0; i < S.length(); i++){
            if(S.substring(i,i+1).equals("(")){
                count += 1;            
                if(count == 1){
                    i_1 = i+1;
                }
            }
            if(S.substring(i,i+1).equals(")")){
                count -= 1;           
                if(count == 0){
                    j_1 = i;
                    s.append(S.substring(i_1,j_1));
                }
            }
        }
        return s.toString();
    }
}

/leetcode提交执行用时内存消耗 10 ms 38.5 MB

解法二：双指针法
一个指针记录最外层左括号的位置，一个指针记录最外层右括号的位置，当匹配到的时候，再把字符串切片相加。

代码如下：

class Solution {
    /**
    *toCharArray()把String转化成char,使用char[]与字符串作比较。
    */
    public String removeOuterParentheses(String S) {
        int i_1 = 0;
        int j_1 = 0;
        int l = 0;
        StringBuffer s = new StringBuffer();
        char[] arrChar = S.toCharArray();
        for(int i = 0; i < arrChar.length; i++){
            if(arrChar[i] == '('){
                i_1 += 1;
            }
            if(arrChar[i] == ')'){
                j_1 += 1;
            }
            if(i_1 == j_1){
				s.append(S.substring(l+1,i));
                l = i + 1;
            }
        }
        return s.toString();
    }
}

/leetcode提交执行用时内存消耗 3 ms 37.1 MB

class Solution {
	/*
	*直接使用String类的substring()获取，再使用equals()作比较。
	*/
    public String removeOuterParentheses(String S) {
        int i_1 = 0;
        int j_1 = 0;
        int l = 0;
        StringBuffer s = new StringBuffer();
        for(int i = 0; i < S.length(); i++){
            if(S.substring(i,i+1).equals("(")){
                i_1 += 1;
            }
            if(S.substring(i,i+1).equals(")")){
                j_1 += 1;
            }
            if(i_1 == j_1){
                    s.append(S.substring(l+1,i));
                    l = i + 1;
                }
        }
        return s.toString();
    }
}

/leetcode提交执行用时内存消耗 15 ms 38.6 MB
通过对比可以发现，把String转化成char后，直接和字符串作比较，比使用equals()函数作比较要快很多，可以有效减少运行时间。

解法三：自定义栈法
既然这个题目归到栈一类了，就加一个栈的方法。栈的定义是基于链接表。方法参考了评论。空间复杂度无敌，超过 100%，时间复杂度一般，30% 左右。

代码如下：

class Solution {
    /**
    *stack
    */
    public String removeOuterParentheses(String S) {
        StringBuffer s = new StringBuffer();
        Stack<Character> stack = new Stack<>();
        int l = 0;
        for(int i = 0; i < S.length(); i++){
            if(S.charAt(i) == '('){
                stack.push(S.charAt(i));
            }
            if(S.charAt(i) == ')'){
                stack.pop();
                if(stack.isEmpty()){
                    s.append(S.substring(l+1,i));
                    l = i + 1;
                }
            } 
        }
        return s.toString();
    }
}

/leetcode提交执行用时内存消耗 11 ms 36 MB