Leetcode – Valid Parentheses

Name: Valid Parentheses
Difficulty: Easy
Description: Return true if the string opens and closes parenthesis in the correct order

Example:

Given "()", return true 
Given "()[]{}", return true
Given "{[]}", return true
Given "(]", return false

The stack data structure is very useful. As long as the character is an opening parenthesis, i.e. ({[, we just keep pushing it onto the stack. When we start encountering closing parenthesis, i.e. ]}), we pop the stack and expect to find the correct opening parenthesis.

bool isValid(string s) {
   if (s.length() < 2) return false;

    stack<char> symbols;

    for(auto symbol: s) {
        if (symbol == '(' || symbol == '[' || symbol == '{') {
            symbols.push(symbol);
            continue;
        }

        if (symbols.empty()) return false;

        switch(symbols.top()) {
            case '(': if (symbol != ')') return false; break;
            case '[': if (symbol != ']') return false; break;
            case '{': if (symbol != '}') return false; break;
            default: return false;
        }

        symbols.pop();
    }

    return symbols.empty();
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s