20. Valid Parentheses

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> closeToOpen = {
            {')', '('},
            {']', '['},
            {'}', '{'},
        };
        stack<char> stk;
        for (const auto& c : s) {
            if (closeToOpen.count(c)) {
                if (!stk.empty() && stk.top() == closeToOpen[c]) stk.pop();
                else return false;
            } else stk.push(c);
        }
        return stk.empty();
    }
};

• T: $O(N)$
• S: $O(N)$