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 ).
Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]
Credits:
Special thanks to @hpplayer for adding this problem and creating all test cases.
class Solution {private:bool isValid(string s){int count=0;for(int i=0;i<s.length();i++){if(s[i]==‘(‘)count++;else if(s[i]==‘)‘){if(count==0)return false;count--;}}return count==0;}vector<string> ret;public:vector<string> removeInvalidParentheses(string s) {unordered_map<string,int> map;queue<string> q;q.push(s);map[s]=1;bool found=false;while(!q.empty()){string str=q.front();q.pop();if(isValid(str)){ret.push_back(str);found=true;}if(found)continue;for(int i=0;i<str.length();i++){if(str[i]!=‘)‘&&str[i]!=‘(‘)continue;//将这个括号从字符串中去除string sub=str.substr(0,i)+str.substr(i+1);if(map.find(sub)==map.end()){q.push(sub);map[sub]=1;}}}return ret;}};
301.Remove Invalid Parentheses
原文：http://www.cnblogs.com/zhoudayang/p/5024435.html