Skip to content

Instantly share code, notes, and snippets.

@paldepind
Last active December 11, 2015 21:28
Show Gist options
  • Save paldepind/4662669 to your computer and use it in GitHub Desktop.
Save paldepind/4662669 to your computer and use it in GitHub Desktop.
C++ solution the problem "Balanced Smileys" in the Facebook Hackecup 2013. No stacks, no recursion. Complexity is O(n).
bool isBalanced(const string message) {
int paransOpen = 0;
int maybeOpen = 0;
int maybeClosed = 0;
char prevChar = 0;
string::const_iterator iter;
for (iter = message.begin(); iter < message.end(); iter++) {
if (*iter == '(') {
if (prevChar == ':') {
maybeOpen++;
} else {
paransOpen++;
}
} else if (*iter == ')') {
if (prevChar == ':') {
if (paransOpen > 0) { // <-- Untested fix to problem pointed out to me by Angelo Di Pilla
maybeClosed++;
}
} else {
paransOpen--;
}
} else if (!isalpha(*iter) && *iter != ':' && *iter != ' ') {
return false;
}
if (paransOpen + maybeOpen < 0) {
return false;
}
prevChar = *iter;
}
if (paransOpen + maybeOpen >= 0 &&
paransOpen - maybeClosed <= 0) {
return true;
} else {
return false;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment