Valid Parentheses

EasyStack & Queue

Given a string of brackets (), [], {}, return true if every opening bracket is closed by the matching type in the correct order.

Open problem

Constraints

1 <= s.length <= 10^4
s consists only of the characters ()[]{}

Stack of open brackets

Time O(n)Space O(n)

Push each opening bracket. On a closing bracket, the top of the stack must be its matching opener, otherwise the string is invalid. A valid string ends with an empty stack.

#include <bits/stdc++.h>
using namespace std;

bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> match{{')', '('}, {']', '['}, {'}', '{'}};
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if (st.empty() || st.top() != match[c]) return false;
            st.pop();
        }
    }
    return st.empty();
}