For an online screen, I had a question that would take in a vector of strings, and return a vector of strings indicating whether the input string was a valid combination of []{}()
, where valid means the braces are matching and not interleaved. There are no empty string inputs.
For example, [(())]
is valid, but )
, {
, and {[}]
are invalid.
Note that input is only brackets, output is YES or NO, depending on whether or not the input is only matching brackets.
Also note using namespace std
is required by the online software (hackerrank).
/*
* Increments each value in vec by the delta.
*/
void increment(vector<int> &vec, int delta){
transform(vec.begin(), vec.end(), vec.begin(), [delta](int x){return x+delta;});
}
/*
* Checks if a bracket has been closed, and if it has, checks that it
* was expected to be closed. Returns true if there is an invalid close.
* Note that vectors are in sorted order, since we only add indices when
* a new bracket is opened.
*/
bool check(vector<int> &vec, bool expected){
if(vec.empty()){ //if there are no open brackets, check if we expected one
if (expected){
return true;
}
}
else if(vec.back() == 0){ //if the there is a bracket that was closed, check if we expected that
vec.pop_back();
if (!expected){
return true;
}
}
return false;
}
/*
* Complete the function below.
*/
vector<string> braces(vector<string> values) {
vector<pair<char, char>> bracket_types;
bracket_types.push_back(pair<char, char>('{','}'));
bracket_types.push_back(pair<char, char>('(',')'));
bracket_types.push_back(pair<char, char>('[',']'));
vector<string> results;
for(auto const &str: values){
/* Map of vectors containing integers indicating the number of opening brackets
* seen since each bracket was first seen, minus the number of closing.
* When an index is zero, that means that bracket should be closed, so we
* check it using the check method.
*/
map<char, vector<int> > counts;
for(auto const &c : str){ //iterate over the string of brackets
int incr;
for(auto const &type : bracket_types){ //find which bracket we are using
if (type.first == c){ //if it's an opening bracket, add a new open bracket to the vector
incr = 1;
counts[c].push_back(0);
break;
}
if (type.second == c){ //if it's a closing bracket, set incr to decrement each value
incr = -1;
break;
}
}
for(auto &cnt : counts){ //for all vectors, update values, and check if we have an invalid close.
increment(cnt.second, incr);
if (incr < 0 && check(cnt.second, cnt.first==c)){ //if we closed a bracket, could be invalid, check
cnt.second.push_back(0); //add a bracket to a vector, so that we will have the right return
break;
}
}
}
//Return false if there are unclosed brackets.
results.push_back("YES");
for(auto const &cnt : counts){
if (!cnt.second.empty()){
results.back() = "NO";
}
}
}
return results;
}