1021. 删除最外层的括号

Posted on Edited on In , ,
转载自Leet Code

题目描述

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

我的代码

\(T(N) = O(N)\), \(S(N) = O(N)\)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class MySolution1021 
{
	Stack<Character> stack = new Stack();
	
    public String removeOuterParentheses(String S) 
    {
    	String ans = "";
    	
    	for (int i=0; i<S.length(); i++)
    	{
    		Character ch = S.charAt(i);
    		
    		if (ch=='('&&stack.isEmpty())
    			stack.push(ch);
    		else if (ch=='('&&!stack.isEmpty())
    		{
    			ans+=ch;
    			stack.push(ch);
    		}
    		else if (ch==')'&&stack.size()>1)
    		{
    			ans+=ch;
    			stack.pop();
    		}
    		else if (ch==')'&&stack.size()==1)
    			stack.pop();
    	}
    	
    	return ans;
    }
}

方法一：记录层数

\(T(N) = O(N)\), \(S(N) = O(1)\)

对于字符串中的每一个字符， 首先，如果当前字符是右括号则层数减一； 其次，如果当前层数依然大于等于1则在结果中追加当前字符； 最后，如果当前字符是左括号则层数加一。

代码

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution1021
{
    public String removeOuterParentheses(String S) 
	{
        StringBuilder sb = new StringBuilder();
        int level = 0;
        for (char c : S.toCharArray()) 
		{
            if (c == ')') --level;
            if (level >= 1) sb.append(c);
            if (c == '(') ++level;
        }
        return sb.toString();
    }
}

方法二：记录左右括号数目

\(T(N) = O(N)\), \(S(N) = O(1)\)

L：左括号个数，初始化为1；R：右括号个数，初始化为0； 对于字符串中的每一个字符， 如果是左括号则L+1；如果是右括号则R+1； 当R不等于L时，在结果字符串中追加当前字符； 否则，跳过当前字符，并且重置L的值为1、重置R的值为0.

代码

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution1021
{
    public String removeOuterParentheses(String S) 
	{
        int L = 1; int R = 0;
        String ans = "";
        for(int i=0; i<S.length(); i++)
        {
        	if (S.charAt(i)=='(') L++;
        	else R++;
        	
        	if(R!=L) ans+=S.charAt(i);
        	else
        	{
        		i++; L=1; R=0;
        	}
        }
        return ans;
    }
}