Created
February 18, 2018 07:54
-
-
Save jianminchen/3d2f70c349487700bb206a8622ad7827 to your computer and use it in GitHub Desktop.
Remove invalid parentheses - cpp solution to review
This file contains 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