Created
February 18, 2018 07:54
Remove invalid parentheses - cpp solution to review
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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