-
Notifications
You must be signed in to change notification settings - Fork 0
/
1021. Remove Outermost Parentheses.cpp
67 lines (55 loc) · 2.24 KB
/
1021. Remove Outermost Parentheses.cpp
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// 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 = P_1 + P_2 + ... + P_k, where P_i 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: "(()())(())"
// 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
// 来源:力扣(LeetCode)
// 链接:https://leetcode-cn.com/problems/remove-outermost-parentheses
// 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
string removeOuterParentheses(string S) {
string res;
stack<int> indexStack;
for(int j=0;j<S.size();++j)
{
if(S[j]=='(')
{
indexStack.push(j);
}
else
{
int i=indexStack.top();
indexStack.pop();
if(indexStack.size()==0)
{
res+=S.substr(i+1,j-i-1);
}
}
}
return res;
}
};