LeetCode [301] Remove Invalid Parentheses

301. Remove Invalid Parentheses

Hard

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

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

class Solution { bool isvalid(string s){ int cnt = 0; for(auto c:s){ cnt += c=='('; cnt -= c==')'; if(cnt<0) return false; } return cnt==0; } public: vector<string> removeInvalidParentheses(string s) { int l = 0, r = 0; for(auto c:s){ if(c=='(') l++; else{ if(l==0) r += (c==')'); else l -= (c==')'); } } vector<string> ret; dfs(s, ret, 0, l, r); return ret; } void dfs(string s, vector<string>&ret, int pos, int l, int r){ if(l==0 && r==0 && isvalid(s)){ ret.push_back(s); return; } for(int i=pos; i<s.size(); ++i){ if(i>pos && s[i]==s[i-1]) continue; if(!(s[i]=='(' && l>0 || s[i]==')' && r>0)) continue; string s1 = s; s1.erase(i, 1); if(s[i]=='(' && l>0) dfs(s1, ret, i, l-1, r); else if(s[i]==')' && r>0) dfs(s1, ret, i, l, r-1); } } };

• http://zxi.mytechroad.com/blog/string/leetcode-301-remove-invalid-parentheses/