20 Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

• Using a stack is a very natural solution in maintaining valid amounts of inverses.

bool isOpening(char i) {
    return (i == '[' || i == '(' || i == '{');
}

// need explicitly b/c i need to ignore other nonsense chars
bool isClosing(char i) {
    return (i == ']' || i == ')' || i == '}');
}

bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> brackets = {
        {  ']' , '['  },{  ')' , '('  },{  '}' , '{'  }
    };

    for (auto i : s) {
        if (isOpening(i)) {
            st.push(i);
        }
        else {
            if (!st.empty() && isClosing(i) && brackets.find(i)->second == st.top()) {
                st.pop();
            }
            else if (!isClosing(i) && !isOpening(i)) continue;
            else return false;
        }
    }

    return st.empty();
}


int main(int argc, char **argv) {

    string test = "{}{}{}";
    cout << boolalpha << isValid(test) << endl;

    test = "]";
    cout << boolalpha << isValid(test) << endl;

    test = "{";
    cout << boolalpha << isValid(test) << endl;

    test = "{]fdfdfdd";
    cout << boolalpha << isValid(test) << endl;

    test = "{[}]";
    cout << boolalpha << isValid(test) << endl;

    test = "dsd{()()[]}";
    cout << boolalpha << isValid(test) << endl;
}

Constant Space Solution

• Limitations: Only works with brackets of the same type e.g. ()() or [].

• The idea is the same: I am counting the number of opening and closing parathesis types. In the end, the number of opening parathesis should match the number of closing paranthesis.

• The check for (counter < 0) ensures that if a closing paranthesis ever comes before a opening, then the counter would be negative, and we cannot have that. Likewise, in the stack method.

bool isOpening(char i) {
    return (i == '[' || i == '(' || i == '{');
} // checks opening

bool isClosing(char i) {
    return (i == ']' || i == ')' || i == '}');
} // checks closing

const unordered_set<char> allowed = {
    '[' ,']', '(' , ')','{' , '}'
}; // set of allowed parathesis types

   /*
   Uses a counter to increment or decrement the number of
   opening or closing paranthesis respectively.

   Effectively works in a similiar way using the stack
   method.
   */
bool isValid(const string &s) {
    int counter = 0;

    for (char c : s) {
        if (allowed.find(c) == allowed.end()) continue;
        if (isOpening(c)) counter++;
        else if (isClosing(c)) counter--;
        if (counter < 0) return false;
    }

    return counter == 0;
}


int main()
{
    string test;

    test = "))((";
    cout << boolalpha << isValid(test) << endl; // true

    test = "{}fdfdfdd";
    cout << boolalpha << isValid(test) << endl; // true

    test = "{}{sdsd}{}";
    cout << boolalpha << isValid(test) << endl; // true

    test = "]";
    cout << boolalpha << isValid(test) << endl; // false

    test = "{";
    cout << boolalpha << isValid(test) << endl; // false

    test = "(())";
    cout << boolalpha << isValid(test) << endl; // true

    test = "()()()(())()()(()))";
    cout << boolalpha << isValid(test) << endl; // false

    test = "(()(()))";
    cout << boolalpha << isValid(test) << endl; // true
}