20. Valid Parentheses

class Solution {
public:
    bool isValid(string s)
    {
        stack<int> stk;
        unordered_map<char, char> m = {
            {')', '('},
            {']', '['},
            {'}', '{'},
        };

        for (auto c : s)
        {
            if (m.count(c))
            {
                if (!stk.empty() && stk.top() == m[c]) stk.pop();
                else return false;
            }
            else stk.push(c);
        }
        return !stk.size();
    }
};

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