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
| class Solution { public: vector<string> removeInvalidParentheses(string s) { int l = 0, r = 0; for (char c : s) { if (c == '(') l++; else if (c == ')') { if (l == 0) r++; else l--; } } helper(s, "", 0, l, r); vector<string> temp; int len = INT_MIN; for (string s: result) { len = max(static_cast<int>(s.size()), len); } for (string s: result) { if (s.size() == len) { temp.push_back(s); } } return temp; } void helper(string &s, string one, int index, int left, int right) { if (index == s.size()) { if (left == 0 && left == right && valid(one)) { result.insert(one); } return; } if (left < 0 || right < 0) return; if (s[index] != '(' && s[index] != ')') { helper(s, one+s[index], index+1, left, right); return; } int l = 0, r = 0; if (s[index] == '(') l=1; if (s[index] == ')') r=1; helper(s, one, index+1, left-l, right-r); helper(s, one+s[index], index+1, left, right); } bool valid(string & p) { int count = 0; for (char c : p) { if (c == '(') count++; if (c == ')') count--; if (count < 0) return false; } return true; } int min_len = INT_MAX; unordered_set<string> result; };
|