[LeetCode] 1021. Remove Outermost Parentheses

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.

删除最外层的括号。

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

如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-outermost-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题不难，但是题目描述写的不好，只有最后一句话是有用的，就是请你把 input 字符串按照原语的定义，移除最外层的一对括号。比如第一个例子是可以分解成 s = a + b 的形式的，那么我们就返回a + b移除了最外层的括号之后的结果；第三个例子不可以分解成 s = a + b 的形式，那么我们就对 a 和 b 分别移除他们最外层的括号。

思路是用类似 stack 的思想去 track 到底有几层，只有当层数 >= 1 的时候才需要保存遍历到的括号。

时间O(n)

空间O(1)

Java实现

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

LeetCode 题目总结

[LeetCode] 1021. Remove Outermost Parentheses

推荐阅读