Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created February 18, 2018 07:54
Show Gist options
  • Save jianminchen/3d2f70c349487700bb206a8622ad7827 to your computer and use it in GitHub Desktop.
Save jianminchen/3d2f70c349487700bb206a8622ad7827 to your computer and use it in GitHub Desktop.
Remove invalid parentheses - cpp solution to review
class Solution {
public:
bool isParen(char ch)
{
return ch == ')' || ch == '(';
}
bool isValid(string s)
{
// if(s.size() == 0)
// return false;
int closeParencount = 0;
for(auto ch : s)
{
if(isParen(ch))
{
if(ch == ')')
closeParencount--;
else
closeParencount++;
if(closeParencount < 0)
return false;
}
}
return closeParencount == 0;
}
vector<string> removeInvalidParentheses(string s){
bool perfectstrlenfound = false;
vector<string> res;
queue<string> Q;//front and then pop
unordered_set<string> UM;//for checking the duplicatoin.
if(s.size() == 0)
{
res.push_back("");
return res;//.emplace_back("");
}
if(isValid(s))
{
res.push_back(s);
return res;
}
Q.push(s);
while(!Q.empty())
{
string curstr = Q.front();
Q.pop();
//cout << " curstr is " << curstr << endl;
if(isValid(curstr))
{
//cout << "Found the perfect string " << curstr ;
res.push_back(curstr);
perfectstrlenfound = true;
continue;
}
if(perfectstrlenfound)
continue;
for(int i = 0; i < curstr.size(); i++)
{
if(!isParen(curstr[i]))
continue;
string newstr = curstr.substr(0,i) + curstr.substr(i+1);
// cout << "newstr is " << newstr << endl;
if(!UM.count(newstr))
{
Q.push(newstr);
UM.insert(newstr);
}
}
}
return res;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment