https://leetcode.com/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-interview-150

C++

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

        for (char c : s) {
            // closing bracket
            if (match.count(c)) {
                if (st.empty() || st.top() != match[c]) return false;
                st.pop();
            // opening bracket
            } else {
                st.push(c);
            }
        }

        return st.empty();
    }
};

Complexity analysis

• Time complexity : $O(n)$ because we simply traverse the given string one character at a time and push and pop operations on a stack take $O(1)$ time.
• Space complexity : $O(n)$ as we push all opening brackets onto the stack and in the worst case, we will end up pushing all the brackets onto the stack. e.g. ((((((((((.