31. Valid Parentheses

class Solution:
    def isValid(self, s: str) -> bool:
        pair = {')': '(', ']': '[', '}': '{'}
        stack = []
        for ch in s:
            if ch in pair:
                if not stack or stack.pop() != pair[ch]:
                    return False          # wrong or missing opener
            else:
                stack.append(ch)
        return not stack                  # nothing left unclosed

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') stack.push(ch);
            else {
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if ((ch == ')' && open != '(') || (ch == ']' && open != '[') || (ch == '}' && open != '{')) return false;
            }
        }
        return stack.isEmpty();
    }
}

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (char ch : s) {
            if (ch == '(' || ch == '[' || ch == '{') st.push(ch);
            else {
                if (st.empty()) return false;
                char open = st.top(); st.pop();
                if ((ch == ')' && open != '(') || (ch == ']' && open != '[') || (ch == '}' && open != '{')) return false;
            }
        }
        return st.empty();
    }
};

function isValid(s) {
  const pair = { ')': '(', ']': '[', '}': '{' }, stack = [];
  for (const ch of s) {
    if (ch in pair) { if (stack.pop() !== pair[ch]) return false; }
    else stack.push(ch);
  }
  return stack.length === 0;
}