1021. 删除最外层的括号
1021. 删除最外层的括号
题目
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 ofs
.
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 <= 10^5
s[i]
is either'('
or')'
.s
is a valid parentheses string.
题目大意
题目要求去掉最外层的括号。
解题思路
用栈模拟,当遇到 (
时入栈,当遇到 )
时入栈,只有当栈内元素个数大于 1
时(去掉最外层的括号),才将当前字符累加到输出的字符串 str
上。
代码
/**
* @param {string} s
* @return {string}
*/
var removeOuterParentheses = function (s) {
let stack = [];
let str = '';
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
stack.push(s[i]);
if (stack.length > 1) {
str += s[i];
}
} else if (s[i] === ')') {
if (stack.length > 1) {
str += s[i];
}
stack.pop();
}
}
return str;
};