LeetCode-removeOuterParentheses

阳光穿透心脏的1/2处 2023-06-13 12:29 2阅读 0赞

# 问题描述 #

概括一下就是去除由多层括号组成的字符串中最外层的括号。以下是原文描述：  
Return `S` after removing the outermost parentheses of every primitive string in the primitive decomposition of `S`.

Example 1:

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

Example 2:

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

Example 3:

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

Note:

S.length <= 10000
    S[i] is "(" or ")"
    S is a valid parentheses string

# 解决办法 #

匹配括号是栈的非常经典的用法  
基本的思路是：

1.  遍历字符串的每个字符，
2.  如果是`（`，如果栈为空，则说明推入的`(`一定是最外层的一个数据，如果不为空，则输出此`(`
3.  如果是`)`，说明栈内一定有数据，从栈内取出一个字符串，如果取出字符串后，栈不为空，则说明不是最外层的括号，则输出`)`；如果此时栈为空，则说明这对`()`是最外层的，则不输出。

# 代码 #

public class RemoveOuterParentheses {
    
        public String removeOuterParentheses(String S) {
            Stack<Character> stack = new Stack<>();
            StringBuffer str = new StringBuffer();
    
            char[] ss = S.toCharArray();
            for(char c: ss) {
                if ('(' == c) {
                    if (!stack.empty()) {
                        str.append(c);
                    }
                    stack.push(c);
                }
    
                if (')' == c) {
                    stack.pop();
                    if (!stack.empty()) {
                        str.append(c);
                    }
                }
            }
            return str.toString();
        }
    }

如果小伙伴们有更好的解决办法，欢迎留言探讨。

LeetCode-removeOuterParentheses

发表评论取消回复

还没有评论，来说两句吧...

相关阅读