Valid Parentheses

Approach: Stack#

A closing bracket is only valid if it matches the most recently opened bracket — a classic LIFO relationship that maps directly to a stack. Scan characters left to right: push every opening bracket ((, {, [) onto the stack. When a closing bracket is encountered, check whether the stack's top holds the matching opener; if it does, pop it; if not (or if the stack is empty), the string is invalid. After the full scan, a valid string has no unmatched openers left, so return stk.empty().

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;

        for(char c: s)
        {
            if(c=='(' || c=='{' || c=='[')
                stk.push(c);
            else {
                if(stk.empty() || (c==')' && stk.top()!='(') || (c=='}' && stk.top()!='{') || (c==']' && stk.top()!='['))
                    return false;
                stk.pop();
            }

        }
        return stk.empty();
    }
};

Time Complexity: O(n)

Space Complexity: O(1)