LeetCode（Stack)1021. Remove Outermost Parentheses

素颜马尾好姑娘i 2023-09-25 22:48 98阅读 0赞

# 1.问题 #

A valid parentheses string is either empty “”, “(” + A + “)”, or A + B, where A and B are valid parentheses strings, and + represents string concatenation.

*  For example, “”, “()”, “(())()”, and “(()(()))” are all valid parentheses strings.  
    A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + … + Pk, where Pi are primitive valid parentheses strings.

Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.

Example 1:

> Input: s = “(()())(())”  
> Output: “()()()”  
> Explanation:  
> The input string is “(()())(())”, with primitive decomposition “(()())” + “(())”.  
> After removing outer parentheses of each part, this is “()()” + “()” = “()()()”.

Example 2:

> Input: s = “(()())(())(()(()))”  
> Output: “()()()()(())”  
> Explanation:  
> The input string is “(()())(())(()(()))”, with primitive decomposition “(()())” + “(())” + “(()(()))”.  
> After removing outer parentheses of each part, this is “()()” + “()” + “()(())” = “()()()()(())”.

Example 3:

> Input: s = “()()”  
> Output: “”  
> Explanation:  
> The input string is “()()”, with primitive decomposition “()” + “()”.  
> After removing outer parentheses of each part, this is “” + “” = “”.

Constraints:

*  1 <= s.length <= 105
 *  s\[i\] is either ‘(’ or ‘)’.
 *  s is a valid parentheses string.

# 2. 解题思路 #

## 方法1： ##

> 1.遍历字符串 s 中的每个字符，如果当前字符是左括号，则将其入栈；  
> 2.如果当前字符是右括号，则将其入栈。  
> 3.在遍历过程中，我们统计左括号和右括号的数量，如果左括号数量等于右括号数量，则说明我们找到了一个原语，此时将栈中除去最外层括号的所有字符取出，添加到结果字符串中。  
> 4.然后清空栈，重新开始计数。  
> **需要注意的是**，在取出栈中除去最外层括号的所有字符时，我们需要从栈中的第二个字符开始取，直到倒数第二个字符结束。这是因为最外层的左括号和右括号已经在统计左右括号数量的时候被计算了，不需要再添加到结果字符串中。

## 方法2： ##

>  *  同样使用栈来判断是否为最外层括号，不同的是，对于最外层的括号，我们不需要将其添加到结果字符串中，只需要忽略掉即可。
>  *  在遍历字符串 s 的过程中，如果当前字符是左括号，我们先判断栈中是否有元素。如果栈中已经有元素，说明该左括号不是最外层的，将其添加到结果字符串中。然后将该左括号入栈。
>  *  如果当前字符是右括号，弹出栈顶元素，然后判断栈中是否还有元素。如果栈中还有元素，说明该右括号不是最外层的，将其添加到结果字符串中

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public String removeOuterParentheses(String s) {
        
            StringBuffer str = new StringBuffer(); // 定义一个 StringBuffer 变量 str，用于存储结果字符串
            Stack<Character> stack= new Stack<>(); // 定义一个 Stack 变量 stack，用于存储左括号
            int leftSum=0; // 定义一个变量 leftSum，用于统计左括号的数量
            int rightSum =0; // 定义一个变量 rightSum，用于统计右括号的数量
            for(char ch: s.toCharArray()){
         // 遍历字符串 s 中的每个字符
                if(ch=='('){
         // 如果当前字符是左括号
                    leftSum++; // 左括号数量加 1
                    stack.push(ch); // 将左括号压入栈中
                }else{
         // 如果当前字符是右括号
                    rightSum++; // 右括号数量加 1
                    stack.push(ch); // 将右括号压入栈中
                }
                if(leftSum==rightSum){
         // 如果左括号数量等于右括号数量
                    for (int i = 1; i < stack.size()-1; i++) {
         // 遍历栈中除去最外层括号的所有字符
                        str.append(stack.get(i)); // 将当前字符添加到结果字符串中
                    }
                    stack.clear(); // 清空栈
                    leftSum = 0; // 左括号数量清零
                    rightSum = 0; // 右括号数量清零
                }
            }
            return str.toString(); // 返回结果字符串
        }
    }

## 代码2： ##

class Solution {
        
        public String removeOuterParentheses(String s) {
        
            // 使用栈来存储左括号
            Stack<Character> bracket = new Stack<>();
            // 使用 StringBuilder 存储结果字符串
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
        
                if (s.charAt(i) == '(') {
        
                    // 如果是左括号，如果栈中已经有元素，说明该左括号不是最外层的，将其添加到结果字符串中
                    if (bracket.size() > 0) {
        
                        sb.append(s.charAt(i));
                    }
                    // 将左括号入栈
                    bracket.push(s.charAt(i));
                } else {
        
                    // 如果是右括号，弹出栈顶元素
                    bracket.pop();
                    // 如果栈中还有元素，说明该右括号不是最外层的，将其添加到结果字符串中
                    if (bracket.size() > 0) {
        
                        sb.append(s.charAt(i));
                    }
                }
            }
            return sb.toString();
        }
    }

> 该解法使用了一个计数器 count 来统计当前括号的嵌套深度，即左括号的数量减去右括号的数量。  
> 遍历输入字符串 s 的每个字符，当遇到左括号时，如果当前嵌套深度大于1，则将其加入结果字符串 sb 中；当遇到右括号时，如果当前嵌套深度大于1，则将其加入结果字符串 sb 中。  
> 最后返回结果字符串 sb 即可。

class Solution {
        
        public String removeOuterParentheses(String s) {
        
            
            int count = 0; // 统计当前括号的嵌套深度，即左括号的数量减去右括号的数量
    		StringBuilder sb = new StringBuilder(); // 用于存储最终结果的字符串
    		
    		for (char c : s.toCharArray()) {
        
    
    			if (c == '(' && count++ > 0) {
         // 遇到左括号，如果当前嵌套深度大于1，则将其加入结果字符串中
                    sb.append(c);
                }
    			if (c == ')' && --count > 0) {
         // 遇到右括号，如果当前嵌套深度大于1，则将其加入结果字符串中
                    sb.append(c);
                }
    			
    		}
    		
    		return sb.toString(); // 返回结果字符串
        }
    }