-
Notifications
You must be signed in to change notification settings - Fork 0
/
InvalidParentheses.cpp
79 lines (72 loc) · 2.18 KB
/
InvalidParentheses.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
68
69
70
71
72
73
74
75
76
77
78
79
#include "bits/stdc++.h"
using namespace std;
class Solution {
public:
void fillStack(string s, stack<pair<char, int>> &st) {
for (int i = 0; i < s.length(); i++) {
if (st.empty() && (s[i] == '(' || s[i] == ')')) {
st.push({s[i], i});
} else if (s[i] == ')' && st.top().first == '(') {
st.pop();
} else if (s[i] == '(' || s[i] == ')') {
st.push({s[i], i});
}
}
}
void removeUtil(string s, stack<pair<char, int>> st, int ind, unordered_set<string> &ans, vector<int> &toErase) {
if (ind == 0 || st.empty()) {
// cout << s << " " << st.size() << endl;
if (st.empty()) {
for (auto ele : toErase) s.erase(ele, 1);
ans.insert(s);
}
return;
}
pair<char, int> temp = st.top();
if (s[ind] == '(') {
if (temp.first == '(' && temp.second <= ind) {
toErase.push_back(ind);
st.pop();
removeUtil(s, st, ind - 1, ans, toErase);
st.push(temp);
toErase.pop_back();
}
} else if (s[ind] == ')') {
if (temp.first == ')' && temp.second >= ind) {
toErase.push_back(ind);
st.pop();
removeUtil(s, st, ind - 1, ans, toErase);
st.push(temp);
toErase.pop_back();
}
}
removeUtil(s, st, ind - 1, ans, toErase);
}
vector<string> removeInvalidParentheses(string s) {
unordered_set<string> vec;
vector<string> ans;
stack<pair<char, int>> st;
fillStack(s, st);
vector<int> toErase;
removeUtil(s, st, s.length() - 1, vec, toErase);
for (auto ele : vec) {
ans.push_back(ele);
}
return ans;
}
};
int main() {
int t; cin >> t;
while (t--) {
string s;
cin >> s;
Solution sol;
vector<string> ans;
ans = sol.removeInvalidParentheses(s);
for (auto ele : ans) {
cout << ele << endl;
}
cout << endl;
}
return 0;
}